# 2020q3 Homework6 (quiz6)
contributed by < `Uduru0522` >

###### tags: `perspective and application of computer systems 2020`

---

## 測驗一： float32 / bfloat16 轉換
:::success

#### 轉換程式：

float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= 0xFF800000;
    r /= 256;
    y = x + r;

    *py &= 0xFFFF0000;
    return y;
}

:::
## 程式說明
### 為了 bitwise operation 的強制轉換

int *py = (int *) &y;

由於 bitwise operators 僅定義在 integer 之上，
> C99 Standard, §6.5.7, §6.5.10~6.5.12
> > **Constrains:** Each of the operands shall have integer type.

因此進行強制轉型。此種把某型別的值當作其他型別來使用的行為，稱作 **Type Punning**
然爾，在搜尋關於這種轉型的資訊時，發現這種轉型會違反 Strict Aliasing Rules，有可能造成 Undefined Behavior。

#### Strict Aliasing Rules
> C99 Standard, §6.5/7
> > **An object shall have its stored value accessed only by an lvalue expression that has one of the following types:**
> > + a type compatible with the effective type of the object,
> > + a qualified version of a type compatible with the effective type of the object,
> > + a type that is the signed or unsigned type corresponding to the effective type of the object,
> > + a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
> > + an aggregate or union type that includes one of the aforementioned types among its members (including, recursively,amember of a subaggregate or contained union), or
> > + a character type.

以上規則被稱為 *Strict Aliasing Rules*，
否則可能由於 Compiler 在 -fstrict-aliasing 啟用時(e.g., -O2)，因**默認不會有除了符合上述規定的兩個相異指標指向同一個記憶體位置 (aliasing)**，而造成非預期的結果.
:::info
**範例**

#include <stdio.h>

int foo(float *f, int *i)
{
    *i = 1;
    *f = 0.f;
   
   return *i;
}

int main()
{
    int x = 0;
    
    printf("x = %d\n", x);
    x = foo((float *)&x, &x);
    printf("x = %d\n", x);

    return 0;
}

**預想**
在 `foo()` 中，由上至下執行，`x` 的記憶體內容被修改至 1，再修改成零，最後回傳。

**測試**
分別以 `gcc -o a1.out <filename>` 以及 `gcc -o a2.out <filename> -O2` 編譯並執行，可以得到兩種不同的結果，如圖：

**分析**
至 [<u>Compiler Explorer 上進行比較</u>](https://godbolt.org/z/TM36qM)，觀察啟用 -O2 的結果：

foo:
        mov     DWORD PTR [rsi], 1
        mov     eax, 1
        mov     DWORD PTR [rdi], 0x00000000
        ret
.LC1:
        .string "x = %d\n"
main:
        sub     rsp, 8
        xor     esi, esi
        mov     edi, OFFSET FLAT:.LC1
        xor     eax, eax
        call    printf
        mov     esi, 1
        mov     edi, OFFSET FLAT:.LC1
        xor     eax, eax
        call    printf
        xor     eax, eax
        add     rsp, 8
        ret

可以看到，`<foo>`之中，因編譯器默認我會遵守 Strict Alias Rule,
假定 `*f` 以及 `*i` 不會指向同一記憶體，
a.k.a. 可以直接在修改 `*i` 後扔至 $eax。
:::

#### 替代的轉換方案
+ (Standard) `memcpy()` --- C: Valid, C++: Valid

uint32_t func_memcpy(float f){
    uint32_t n;
    memcpy(&n, &f, sizeof(f)); // OK
    printf("%" PRIu32 "\n", n);
    return n;
}

+ `union` C: Valid, C++: UB

uint32_t func_union(float f){
    union{
        float f;
        uint32_t n;
    }u;

    u.f = f;
    // n is not activated in c++, thus UB
    printf("%" PRIu32 "\n", u.n); 
    return u.n;
}

### 判斷形式
以下為 bfloat16 的數字表達形式：

| **Exponent** | **Sigificand == 0** | **Significand != 0** | **Equation** |
| :-: | :-: | :-: | :-: |
| $00_H$ | $\pm 0$ | Denormalized | $(-1)^{\text{signbit}}\times 2^{-126}\times 0.\text{significand}$ |
| $01_H \sim FE_H$ | Normalized | Normalized | $(-1)^{\text{signbit}}\times 2^{\text{exponent}-127}\times 1.\text{significand}$ |
| $FF_H$ | $\pm \infty$ | Not a Number | **---** |
+ 由於 0，NaN 以及無限的表示方式與 float32 一致，第 5~10 行進行 Earty Retrun。
+ 再者，由於使用的 bias 相同 (-127)，再將 significand 捨入至剩下 7 bit 即可。

### 處理進位
此程式碼使用四捨五入進至小數點後第七位的方式處理多餘的 bit.

    float r = x;
    int *pr = (int *) &r;
    *pr &= 0xFF800000;
    r /= 256;
    y = x + r;
    
    *py &= 0xFFFF0000;

設 `x` 為 $k\times 2^n$，`r` 便會是 $1\times 2^{n - 8}$，又或者可以說是 $0.00000001_2\times 2^n$。
直接加上 `x` 之後，就有四捨五入的效果。
最後，再以 `0xFFFF0000` 取得前十六個位元回傳。

## 延伸問題
### 制作 DP/SP 轉換程式，並針對 BFloat16 撰寫測試程式

### 考慮批次轉換 FP32/FP64，提高轉換效率

---

## 測驗二： Ring Buffer
:::success

#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME

#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + 1) : 0)
#define NEXT_END_INDEX(BUF) \
    (((BUF)->end != (BUF)->size) ? ((BUF)->end + 1) : 0)

#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF)                   \
    do {                                          \
        (BUF)->end = NEXT_END_INDEX(BUF);         \
        if (is_ringbuf_empty(BUF))                \
            (BUF)->start = NEXT_START_INDEX(BUF); \
    } while (0)

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

#define ringbuf_write(BUF, ELEMENT)        \
    do {                                   \
        ringbuf_write_peek(BUF) = ELEMENT; \
        ringbuf_write_skip(BUF);           \
    } while (0)

#define ringbuf_read(BUF, ELEMENT)        \
    do {                                  \
        ELEMENT = ringbuf_read_peek(BUF); \
        ringbuf_read_skip(BUF);           \
    } while (0)

:::spoiler 測試程式

:::
## 程式說明
:::info
以 `gcc -E -P ring_buffer.c > ring_buffer_extended.c`
將上方測試程式展開進行說明。
> -E: 僅 Preprocess
> -P: Preprocess Option, 不在產出的信息中標注展開來源
:::spoiler 完整程式碼

void __attribute__((__cdecl__)) __attribute__((__nothrow__)) _assert(const char *, const char *, int) __attribute__((__noreturn__));
typedef struct
{
    int size;
    int start, end;
    int *elements;
} int_buf;
int main()
{
    int_buf my_buf;
    {
        static int static_ringbuf_mem[2 + 1];
        my_buf.elements = static_ringbuf_mem;
    }
    my_buf.size = 2;
    my_buf.start = 0;
    my_buf.end = 0;
    ;
    ((((&my_buf)->end == (&my_buf)->start)) ? (void)0 : _assert("is_ringbuf_empty(&my_buf)", "ring_buffer.c", 56));
    do
    {
        (&my_buf)->elements[(&my_buf)->end] = 37;
        do
        {
            (&my_buf)->end = (((&my_buf)->end != (&my_buf)->size) ? ((&my_buf)->end + 1) : 0);
            if (((&my_buf)->end == (&my_buf)->start))
                (&my_buf)->start = (((&my_buf)->start != (&my_buf)->size) ? ((&my_buf)->start + 1) : 0);
        } while (0);
    } while (0);

    do
    {
        (&my_buf)->elements[(&my_buf)->end] = 72;
        do
        {
            (&my_buf)->end = (((&my_buf)->end != (&my_buf)->size) ? ((&my_buf)->end + 1) : 0);
            if (((&my_buf)->end == (&my_buf)->start))
                (&my_buf)->start = (((&my_buf)->start != (&my_buf)->size) ? ((&my_buf)->start + 1) : 0);
        } while (0);
    } while (0);
    
    ((!((&my_buf)->end == (&my_buf)->start)) ? (void)0 : _assert("!is_ringbuf_empty(&my_buf)", "ring_buffer.c", 60));
    int first;
    do
    {
        first = (&my_buf)->elements[(&my_buf)->start];
        (&my_buf)->start = (((&my_buf)->start != (&my_buf)->size) ? ((&my_buf)->start + 1) : 0);
        ;
    } while (0);
    ((first == 37) ? (void)0 : _assert("first == 37", "ring_buffer.c", 64));
    int second;
    do
    {
        second = (&my_buf)->elements[(&my_buf)->start];
        (&my_buf)->start = (((&my_buf)->start != (&my_buf)->size) ? ((&my_buf)->start + 1) : 0);
        ;
    } while (0);
    ((second == 72) ? (void)0 : _assert("second == 72", "ring_buffer.c", 68));
    return 0;
}

:::
### Ring Buffer
此程式對 Ring Buffer 進行實作 (又稱為 Circular Buffer)，

我們可以當作一個**有大小上限**的 queue，當其為滿時，
push 會覆蓋住原先會第一個被 pop 掉的元素。。
此實作以 `start` 指向起點(下次提取的位置)，`end` 指向尾端(下個填入的位置)。

### 宣告及初始化

#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME
#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

利用 macro，我們便可定義任意一種 type 的 Ring Buffer。
初始化時，我們取得 n + 1 個元素大小的記憶體，如此一來，配合而後的程式碼，
**僅有 Buffer 為空時會發生 `start == end` 的情況**。

### 新增資料
初始化完成後，填入 "37"：

do
    {
        (&my_buf)->elements[(&my_buf)->end] = 37;
        do
        {
            (&my_buf)->end = (((&my_buf)->end != (&my_buf)->size) ? ((&my_buf)->end + 1) : 0);
            if (((&my_buf)->end == (&my_buf)->start))
                (&my_buf)->start = (((&my_buf)->start != (&my_buf)->size) ? ((&my_buf)->start + 1) : 0);
        } while (0);
    } while (0);

+ 初始化後，狀態如下：(最左側 Index=0，右側 Index=2)

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{start \| end|}|{|}|{|}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

+ 首先，直接填入：

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{start \| end|37}|{|}|{|}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

+ 將 `end` 換至下個位置，並判斷 Out Of Bound

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{start|37}|{end|}|{|}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

### Full Buffer 的寫入
假設以下的 Buffer 狀態，欲寫入 "96"：(大小 = 3)

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "deepskyblue"
        label = "{{start|13}|{|21}|{|77}|{end|}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

+ 直接填入 `end` 所在位置

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "deepskyblue"
        label = "{{start|13}|{|21}|{|77}|{end|96}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

+ 移動 `end`

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "deepskyblue"
        label = "{{start \| end|13}|{|21}|{|77}|{|96}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

+ `start == end` 時，移動 `start`

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "deepskyblue"
        label = "{{end|13}|{start|21}|{|77}|{|96}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

如此，由於我們提取元素時從 `start` 開始，形同 13 被覆蓋掉了。

### 提取元素

int first;
    do
    {
        first = (&my_buf)->elements[(&my_buf)->start];
        (&my_buf)->start = (((&my_buf)->start != (&my_buf)->size) ? ((&my_buf)->start + 1) : 0);
        ;
    } while (0);

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{start|37}|{|72}|{end|}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

+ 直接提出 `start` 所在位置的元素，並向前挪移。

digraph structs{
    rankdir = LR
    node[shape = record]

    array[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{|37}|{start|72}|{end|}}"
        fixedsize = "true"
        width = "10"
        height = "1"
        fontname = "Courier New:"
        fontsize = "24"
    ]
}

### assert()
我們可以看到，`assert(EX)` 被展開成以 `?:` 以及 `_assert()` 函式 組成。
打開 `<assert.h>`，可以找下定義，

#define assert(e) ((e) ? (void)0 : _assert(#e, __FILE__, __LINE__))

其中可以發現一個 `(void)0`，搜尋資料後發現，它可以被用在『需要有 Expression，卻不需要在該處做任何事』的狀況。
舉例來說，可以用來定一個**僅在 NDEBUG 沒被定義時啟用**的函式：

#ifdef NDEBUG
#define debug_printf(msg) (void)0;
#else
#define debug_printf(msg) printf(#msg);
#endif

## 延伸問題
### macro 之中 do...while(0) 的用意
假設我們定義一個如下的 macro:

#define foo(x) bar(x); baz(x)

使用時，用以下的方式：

foo(x);

在 macro 定義的最後不補分號 `;`，可以讓它和呼叫函式時的寫法一致
然而可能會造成這種狀況：

if(expression())
    foo(x);

展開後會變成如下:

if(expression())
    bar(x);
baz(x);

很明顯，與預期的不符。因此，在有定義多個 statement 的 macro 時，我們以 `do...while(0)` 包住，就可以達成以下樣子：

if(expression())
    do{
        bar(x);
        baz(x);
    }while(0);

#### 為什麼不使用一組大括號 `{}` 就好？
若我們使用一組大括號，原本的 macro 展開之後會變成這個樣子：

if(expression())
{
    bar(x);
    baz(x);
};
else{ /* ... */ }

在 `if` block 之後必定會出現一個大括號，造成 **dangling else**的情形。如過要避免這個狀況，我們就不能在使用 macro 時後方加上分號，然而會造成程式碼格式不統一的情況。`do...while(0)` 身為一個**必須在後方存在一個分號的 block** 來說最適合這個角色。

:::warning
**//TODO**
查詢對 macro 該使用甚麼動詞 (不是 call)
> 用 "expand" --jserv
:::

### 效能改善

---

## 測驗三： Singly Linked-List 之靜態初始化
:::success

#include <stdio.h>

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

struct llist {
    int val;
    struct llist *next;
};

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        node->next = *head;
        *head = node;	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

int main()
{
    struct llist *list = cons(cons(cons(cons(NULL, 7), 4), 5), 9);
    struct llist *p;
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");

    sort(&list);
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");
    return 0;
}

:::
## 程式說明
linked-list 不特別說明。
此時作的特點在於初始化串列時使用 **compound literal** 來進行。

### Compound Literal

(type){ initializer-list }

引述 [C++ Refrence - C Language / Expressions](https://en.cppreference.com/w/c/language/compound_literal)
> Constructs an unnamed object of specified type in-place, used when a variable of array, struct, or union type would be needed only once.

舉例來說，以下程式碼：

struct foo{
    int i;
    double d;
};

struct foo s = (struct foo){42, 3.14};

和以下相同：

struct foo temp;
temp.i = 42;
temp.d = 3.14;

struct foo s = temp;

其構造中的 initializer-list 需根據 type 的構造，依序填入符合的 Initializer 並以逗號隔開，
各項有以下三個選擇：
1. `expression`
2. `{ initializer-list }`
3. `designator expression` (**After C99**)，用來自訂填入順序。會自該項繼續初始化。
#### 以下範例：

struct bar{
    int bar_i;
}

struct foo{
    int foo_i;
    double foo_d;
    struct bar foo_b;
    int foo_arr[3];
};

struct foo s = (struct foo){
    .foo_d = 3.14,      /* designator expression */   
    (struct bar){42},   /* initializer-list */  
    {[2]=5, [0]=2, 3},  /* list of initializers, with designator expressions */  
    .foo_i = 1337       /* designator expression */
};

首先，指定初始化 `foo_d` 後繼續往下初始化 `foo_b` 以及 `foo_arr`，最後再指定 `foo_i`。
+ 由於 `foo_b` 為一 structure，初始化需要再以 `{}` 圍繞
+ 陣列初始化也需以 `{}` 圍繞

除此之外，Compound Literal 還有以下特性：
+ **為 lvalue**，可以取得記憶體位址
+ 在 block 之中只會被創造一次

int f ()
{
    struct s {int i;} *p = 0, *q;
    int j = 0;
again:
    q = p, p = &((struct s){ j++ });
    if (j < 2) goto again; 

    return p == q && q->i == 1; 
}

> 以上函式回傳 1
> 若第 7 行使用 `while(){}` ，由於會造成 block 結束，Compund Literal 的生命週期結束，
> `*p` 會成為 **danglling pointer**。

### 連接方法
我們可以將以下 macro 的使用

#define cons(x, y) (struct llist[]){{y, x}}
struct llist *list = cons(NULL, 7);

視作：

struct llist temp[1];
temp[0].next = NULL;
temp[0].val = 7;
struct llist *list = temp;

因此可以使用 `cons()` 來進行初始化。

### Insertion Sort
此處在對 linked-list 排序的操作，以 insertion sort 進行。
`sort()` 中，以 `llist *sorted` 儲存以排序完成的部分，且排序為由小排到大。
每個 iteration 將原本的 `head` 切離，放到 `sorted` 之中。

## 延伸問題

---

# 測驗四： LeetCode 287. Find the Duplicate Number
:::success
+ 設陣列長度為 n, 其中會出現 1 ~ (n-1) 的數值
+ 重複者不一定只重復一次

int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (c1 < c2)
            res += bit;
    }
    return res;
}

:::
## 程式說明
### 題目分析
此題輸入的陣列可以用以下的方法生成：
+ **將一 $1 \sim n$ 的連續數列，隨機拿走 $n$ 以及 $k,k\in [0, n-1]$ 個其他數，**
**並補上 k+1 個 $m, m\in [1,n-1]$**

由此出發，我們可以發現，對每個 bit 位置來說，操作後，$m$ 的 set bit 之處，總 set bit 必定相等或者更多。
舉例來說，$[1,2,3,4,5,6,7]\rightarrow [1,2,3,5,6,2,2]$ ($m$ 為 2)

| **SetBit** | [2] | [1] | [0] |
| :-------- | :-: | :-: | :-: |
| **Before** | 1 | 4 | 4 |
| **After** | 0 | 5 | 3 |

程式以 `c1` 計算操作前，`c2` 計算操作後。

### 效率提升

const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) { /* *... */ }

利用 `8 * sizeof(int)` 應對 `int` 非為 32-bit 的情況。
且根據 n, 僅計算會有影響的 bit.

以下為題目程式碼於 LeetCode 上的執行結果。

## 延伸問題
### 指出改進空間
觀察 `for` 迴圈，我們可以看到有大量的 branch 指令會出現，且因為數列沒有規律，
我們可以預想 prediction faliure 會發生許多次。
可以嘗試移除 if：

c1 += !!(k & bit);
c2 += !!(nums[k] & bit);

不過並未影響 LeetCode 上程式執行時間

### 實作相異程式碼
可以考慮使用類似 c++ 中 `std::map` 的方式實作，逕直開一個夠大的 array 省去 hash function：

int findDuplicate(int *nums, int numsSize)
{
    int map[numSize];
    memset(map, 0, sizeof(int) * numsSize);
    
    while(1){
        if(++map[*nums++] > 1){
            return *(--nums);
        }
    }
}