# 2020q3 Homework6 (quiz6)
contributed by <`Tim096`>
[TOC]

## 測驗 1

#include <stdio.h>

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;  //BB1
    r /= 256;
    y = x + r;
    *py &= 0xffff0000;  //BB2
    return y;
}

void print_hex(float x) {
    int *p = (int *)&x;
    printf("%f = %x\n", x, *p);
}

int main() {
    float a[] = {3.140625, 1.2, 2.31, 3.46, 5.63};
    printf("f = x\n");
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
        print_hex(a[i]);
        printf("--------\n");
        float bf_a = fp32tobf16(a[i]);
        print_hex(bf_a);
    }
    return 0;
}

int main() {
    float a[] = {3.140625, 1.2, 2.31, 3.46, 5.63};
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
        print_hex(a[i]);
        float bf_a = fp32tobf16(a[i]);
        print_hex(bf_a);
    }
    return 0;
}

1. sizeof(n)：傳回變數的 bytes 大小
2. 一個 float 4 bytes
3. 在 C 語言中，其實是不能夠對 floating point 作 bitwise 運算的。所以我們必須先把他強制轉型成 int 。才能直接對浮點數作位元操作。

輸出 : 
3.140625=40490000 --- (FP32)
3.140625=40490000 --- (bfloat16)

1.200000=3f99999a --- (FP32)
1.203125=3f9a0000 --- (bfloat16)

2.310000=4013d70a --- (FP32)
2.312500=40140000 --- (bfloat16)

3.460000=405d70a4 --- (FP32)
3.453125=405d0000 --- (bfloat16)

5.630000=40b428f6 --- (FP32)
5.625000=40b40000 --- (bfloat16)

:::danger
Q : 為何 for 迴圈當中的條件(` i < sizeof(a) / sizeof(a[0] `)要搞的那麼麻煩？
A : C 陣列本身沒有儲存陣列大小的資訊。如果想要知道陣列的大小，得自行計算。
:::

void print_hex(float x) {
    int *p = (int *) &x;
    printf("%f=%x\n", x, *p);
}

逐行解釋

>%x : 16進位整數
傳進來的 x 是 float

    int *p = (int *) &x;

強制轉型成 `int *`

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;  //BB1
    r /= 256;
    y = x + r;
    
    *py &= 0xffff0000;  //BB2
    return y;
}

[先備知識](https://www.itread01.com/content/1543589824.html)

`fp32tobf16()` 的功能 : 將 Fraction 0 捨 1 入 到小數點第 7 位

這邊程式解析 [YLowy](https://hackmd.io/@YLowy/SkDR4AIDD) 大神寫的很棒，我就不另外寫了。

---

## 測驗二 [Ring Buffer](https://en.wikipedia.org/wiki/Circular_buffer) 實作

#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 + RB1) : 0)   //RB1 = 1
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)  //RB2 = 1

#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)

其測試程式如下:

#include <assert.h>

RINGBUF_DECL(int, int_buf);

int main()
{
    int_buf my_buf;
    RINGBUF_INIT(my_buf, 2, int);
    assert(is_ringbuf_empty(&my_buf));

    ringbuf_write(&my_buf, 37);
    ringbuf_write(&my_buf, 72);
    assert(!is_ringbuf_empty(&my_buf));

    int first;
    ringbuf_read(&my_buf, first);
    assert(first == 37);

    int second;
    ringbuf_read(&my_buf, second);
    assert(second == 72);

    return 0;
}

### 簡要說明

1. ring buffer 等價於 circular queue
2. ring buffer 有兩個索引 `start` 及 `end` 分別紀錄第一個及最後插入元素的索引。
3. ring buffer 採用 FIFO

### 逐行說明

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

`start` 和 `end` 改指向下一個元素的操作，如果原本 `start` 已經等於 `(BUF)->size` ，那麼下一個元素就會回到 index = 0。

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

ring buffer 寫入時我們分成 2 個步驟
* `ringbuf_write_peek(BUF)`
* 將值寫在 END 指向位置
* `ringbuf_write_skip(BUF)`
* END 往後移動 1 格

#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)

`ringbuf_write_skip(BUF)` : END 往後移動 1 格，之後還要特別注意是否空格已經被佔滿的了，若==是==則把傳進來的新值拋棄掉

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

ring buffer 讀出時我們分成 2 個步驟
* `ringbuf_read_peek(BUF)`
* 讀出 START 該值
* `ringbuf_read_skip(BUF)`
* START 往後移動 1 格

#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

`ringbuf_read_skip(BUF)` : 若 buffer 內的值沒有，因此不用清空，透過 `START` , `END` 就可以知道內部是否存在資料。

### [巨集程式碼解釋 : ](https://hackmd.io/SodF9rqzQV6nqCjHjGpk8w?view#%E6%B8%AC%E9%A9%97%E4%BA%8C-ring-buffer-%E5%AF%A6%E4%BD%9C)

`RINGBUF_DECL(T, NAME)`
輸入 Type(T), buffer name(NAME)，其會建立一 structure 分別包含
1. ring buffer 大小(size)
2. 所存起始位置以及結束位置(start,end)
3. 指向記憶體實體陣列 [0] 位置的 pointer。

`RINGBUF_INIT(BUF, S, T)`
再建立完上述 structure 之後，會先執行初始化。
創立該 type * (size+1) 大小的空間
:::info
size+1 意味著可以將 [ring buffer](https://en.wikipedia.org/wiki/Circular_buffer) 中提到的
>A circular buffer can be implemented using four pointers, or two pointers and two integers:

>1. buffer start in memory
>2. buffer end in memory, or buffer capacity
>3. start of valid data (index or pointer)
>4. end of valid data (index or pointer), or amount of data currently in the buffer (integer)

buffer end in memory 記錄在此，也就是為何我們只需要 3 個 structure 參數即可，也因如此這次實作並未完全依照本篇所提到的架構。

:::

digraph D {
    node_B [shape=record    label="{}|{<s> A}|{B}|{C}|{<e>}|{}|{}|{}"];
    START ->node_B:s
    END ->node_B:e
}

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

`NEXT_XXXX_INDEX(BUF)`
紀錄資料所需要的 START 或者 END 通常會隨著資料內 push 或者 pop 改變位置，而為了確保 ring 結構中，若是下個位置超出該 buffer size 則會回到 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)

`is_ringbuf_empty/full(BUF)`
分別判斷該 buffer 為空或者滿，若成立則回傳 true

**empty**

digraph D {
    node_B [shape=record    label="{}|{<s> }|{}|{}|{<e>}|{}|{}|{}"];
    START ->node_B:s
    END ->node_B:s
}

**full**

digraph D {
    node_B [shape=record    label="{<e>}|{<s> A}|{B}|{C}|{D}|{E}|{F}|{G}"];
    START ->node_B:s
    END ->node_B:e
}

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

### 解釋上述程式碼的運作機制，包含 `do { ... } while (0)` 使用的考量

[仙貝知識](/hcBjD4toSF2PBaSY93Kb_A)好吃

[參考資料](https://loda.hala01.com/2017/06/linux-kernel-dowhile0.html)

誰都知道第一個 while(0) 肯定是不會運行的，因為 while() 括號中的數值等於0，邏輯判定為假，即代碼塊中的 hello world 不會運行，但是 do while(0) 就不一樣了， do while(0) 即使條件不成立，也會拼了老命的去執行一次！

也就是說，為什麼內核代碼要這樣來做，這是因為內核代碼采用 do{}while(0); 這種結構可以保證無論在什麼地方都可以正確的執行一次 ，這就是它用得最妙的地方，否則有時候調試程序的時候，單單的調試語句寫了沒打印其實是很正常的事情，就是用這樣的一種方法定位到錯誤點，順利改正。

do { … } while(0) 巨集是為了避開 dangling else

### 延伸問題
>do { ... } while(0) 巨集是為了避開 dangling else
1. 研讀 [Super Fast Circular Ring Buffer Using Virtual Memory trick](https://medium.com/@abhinavagarwal1996/a-fast-circular-ring-buffer-4d102ef4d4a3)，指出效能改善的機制並用 C99/C11 (可搭配 GNU extension) 重新實作

---

## 測驗三 靜態初始化的 singly-linked list 實作
考慮到以下靜態初始化的 singly-linked list 實作:

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

以前曾經就想過為何寫 link list 沒有比較簡單的作法，所以當時就上網查過了，所以看到這一題的時候感到格外的親切 XDDD

[compound literals](https://www.ptt.cc/man/C_and_CPP/DB9B/DC33/M.1271034153.A.7F9.html)
> 只有在 C99 才能使用

## 測驗四 [LeetCode 287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)

* Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive.
* There is only one duplicate number in `nums`, return this duplicate number.

Constraints :
> 1. 2 <= n <= 3 * 104
> 2. nums.length == n + 1
> 3. 1 <= nums[i] <= n
> 4. All the integers in nums appear only once except for precisely one integer which appears two or more times.

給定一個整數序列，其中會有一個數值重複，請找出。
已知條件：

1. 假設陣列長度為 n，數值的範圍是 1 ~ n−1
2. 重複的數值不一定只重複一次

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 (CCC) // CCC = c1 < c2
            res += bit;
    }
    return res;
}

* 考慮 二進制 ( 以 1 ~ 6 為例 )

==原先==
| Decimal | Binary |
|:-------:|:-------:|
| 1 | 00==1== |
| 2 | 010 |
| 3 | 01==1== |
| 4 | 100 |
| 5 | 10==1== |
| 6 | 110 |
| TOTAL | 333 |

==更改後==
| Decimal | Binary |
|:-------:|:-------:|
| 1 | 00==1== |
| 2 | 010 |
| 3 | 01==1== |
| 4 | 100 |
| 5 | 10==1== |
| 6 | 110 |
| 3 | 01==1== |
| TOTAL | 3==4====4== |

* 程式碼解析：

const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);

* `log_2` : msb 的 1 在 第幾個 bit

> 這邊在數學式子上要特別注意都是從 1 開始算，而不是 0

:::spoiler 補充 by [RusselCK](https://hackmd.io/@RusselCK/sysprog2020_quiz6#Q4-LeetCode-287-Find-the-Duplicate-Number)

Q : 為何使用 `8 * sizeof(int)` 而非 `32` ?
A : 不同架構的 `sizeof(int)` 不同

:::

   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;         //c1=原先
            if (nums[k] & bit)
                ++c2;        //c2=更改後
        }
        if (CCC) // CCC = c1 < c2
            res += bit;
    }

* `#6` : `bit` 是第 `i` 個二進位之 bit
* 逐一檢查每個位置的 bit ：
* 檢查 nums 中的每個數字：
* `c1` : ==原先== 在 `i` 位置的 bit 的統計值
* `c2` : 後來==更改後==的在 `i` 位置的 bit bit 統計值
* `#14`~`#15` : 若 `c1 < c2`，代表該 `i` 位置上 bit 在重複數字中也為 1，因此要加進 `res`

* [效能評估](https://leetcode.com/submissions/detail/413303314/)： 後續做 pref 效能評估

## Q4. 進階題 提出效能更好的程式碼

int findDuplicate(int* nums, int numsSize){
    if(numsSize == 2)
        return 1;
    int hash[numsSize];
    memset(hash, 0, numsSize*sizeof(int));
    while(1){
    if(++hash[*nums++] == 2) 
        return *(--nums);
    }
}

利用 **hash function** 的方法去思考這一題
* 把每一個值都讓他初始化有一個 hash function 的空間
* 若出現過 `0` 次，則 hash function 中為 0
* 若出現過 `1` 次，則 hash function 中為 1
* 若出現過 `2` 次，則 hash function 中為 2
* 出現超過 2 次，則直接回傳。

### 舉例
`nums[] = {1,2,3,3,4,5}`
`numsSize = 5`

初始值 : i = 0 之 hash function
| 1 | ++0 |
| - | - |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 0 |

i = 1 之 hash function
| 1 | 1 |
| - | - |
| 2 | ++0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 0 |

i = 2 之 hash function
| 1 | 1 |
| - | - |
| 2 | 1 |
| 3 | ++0 |
| 4 | 0 |
| 5 | 0 |

i = 3 之 hash function
| 1 | 1 |
| - | - |
| 2 | 1 |
| 3 | ++1 |
| 4 | 0 |
| 5 | 0 |

最後回傳 hash function 中等於 2 的

### 程式解析
#### 事前初始化設定

    if(numsSize == 2)
        return 1;

若 Input 的話只有兩個一定是`1`

    int hash[numsSize];
    memset(hash, 0, numsSize*sizeof(int));

初始化設定 : 把 hash function 建立並且裏頭數字設 `0`

    while(1){
    if(++hash[*nums++] == 2) 
        return *(--nums);
    }

每一次都把這一次傳進來的 nums 那一個位置的 hash function + 1 代表多傳進來過一次了，然後進行下一個位置的值偵測工作，以此類推。
最後回傳 hash function 中第一個達到 `2` 的。

###### tags: `進階電腦系統應用2020` `quiz6`