# 2020q3 Homework6 (quiz6)
contributed by <`Tim096`>
[TOC]
## 測驗 1
```c=
#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;
}
```
```c=
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 陣列本身沒有儲存陣列大小的資訊。如果想要知道陣列的大小，得自行計算。
:::
```c=
void print_hex(float x) {
int *p = (int *) &x;
printf("%f=%x\n", x, *p);
}
```
逐行解釋
>%x : 16進位整數
傳進來的 x 是 float
```c=2
int *p = (int *) &x;
```
強制轉型成 `int *`
```c=
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) 實作
```c=
#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)
```
其測試程式如下:
```c=
#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
### 逐行說明
```c=17
#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。
```c=35
#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 格
```c=25
#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 格，之後還要特別注意是否空格已經被佔滿的了，若==是==則把傳進來的新值拋棄掉
```c=41
#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 格
```c=33
#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 參數即可，也因如此這次實作並未完全依照本篇所提到的架構。
:::
```graphviz
digraph D {
node_B [shape=record label="{}|{<s> A}|{B}|{C}|{<e>}|{}|{}|{}"];
START ->node_B:s
END ->node_B:e
}
```
```c=
#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 位置。
```c=16
#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**
```graphviz
digraph D {
node_B [shape=record label="{}|{<s> }|{}|{}|{<e>}|{}|{}|{}"];
START ->node_B:s
END ->node_B:s
}
```
**full**
```graphviz
digraph D {
node_B [shape=record label="{<e>}|{<s> A}|{B}|{C}|{D}|{E}|{F}|{G}"];
START ->node_B:s
END ->node_B:e
}
```
```c=19
#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 實作:
```c=
#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. 重複的數值不一定只重複一次
```cpp=
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== |
* 程式碼解析：
```cpp=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)` 不同
:::
```cpp=5
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. 進階題 提出效能更好的程式碼
```c=
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 的
### 程式解析
#### 事前初始化設定
```c=2
if(numsSize == 2)
return 1;
```
若 Input 的話只有兩個一定是`1`
```c=4
int hash[numsSize];
memset(hash, 0, numsSize*sizeof(int));
```
初始化設定 : 把 hash function 建立並且裏頭數字設 `0`
```c=6
while(1){
if(++hash[*nums++] == 2)
return *(--nums);
}
```
每一次都把這一次傳進來的 nums 那一個位置的 hash function + 1 代表多傳進來過一次了，然後進行下一個位置的值偵測工作，以此類推。
最後回傳 hash function 中第一個達到 `2` 的。
###### tags: `進階電腦系統應用2020` `quiz6`
Sign in with Wallet
Connect another wallet