---
tags: Linux2020
---
# 2020q3 Homework6 (quiz6)
contributed by < `YLowy` >
## 測驗一 float32 → bfloat16
### 電腦 64 位元架構電腦中如何表示 bfloat16 ?
float 會使用到 4 bytes ，所以我們若是要用 4 bytes 表示精度較低的 bfloat16，可以使用作法 :
```graphviz
digraph D {
node_B [shape=record label="{S}|{M}|{M}|{M}|{M}|{M}|{M}|{M}|{M}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{...}|{...}|{F}|{F}"];
}
```
考量到 S 不變， M 不變， F只需要求前 7 個 另外考慮 rounding
```graphviz
digraph D {
node_B [shape=record label="{S}|{M}|{M}|{M}|{M}|{M}|{M}|{M}|{M}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{0}|{0}|{0}|{0}|{0}|{...}|{...}|{0}|{0}"];
}
```
雖然輸出 type 仍然是 float32，卻是該值在 bfloat16 所表示的值
參照程式碼 :
```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 &= BB1;
r /= 256;
y = x + r;
*py &= BB2;
return y;
}
```
```c=
float fp32tobf16(float x) {
float y = x;
int *py = (int *) &y;
```
integer pointer py 指向一塊整數且該整數記憶體內容與輸入 float x 相同，整數型態方便我們之後運算操作。
```c=4
unsigned int exp, man;
exp = *py & 0x7F800000u;
man = *py & 0x007FFFFFu;
```
exp : 存放該數的 M
```graphviz
digraph D {
node_B [shape=record label="{0}|{M}|{M}|{M}|{M}|{M}|{M}|{M}|{M}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{...}|{...}|{0}|{0}"];
}
```
man : 存放該數的 F
```graphviz
digraph D {
node_B [shape=record label="{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{0}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{F}|{...}|{...}|{F}|{F}"];
}
```
```c=7
if (!exp && !man) /* zero */
return x;
if (exp == 0x7F800000u) /* infinity or NaN */
return x;
```
回傳當輸入為 `0` `NAN` `infinity` 情況
```c=11
/* Normalized number. round to nearest */
float r = x;
int *pr = (int *) &r;
```
與第一步做相同的事情
integer pointer pr 指向一段與輸入 x 值相同的記憶體空間
```c=14
*pr &= 0x007fffff;
r /= 256;
y = x + r;
```
這裡處理 rounding ，由於 bfloat16 表示精度的位元只有 7 位元，所以我們要找到第 8 位元並判斷要不要進位。
第`14`行 : 這邊用到先將原本數值的 F 部分取出，並且表達成為 denormalized number 形式。
第`15`行 : 將此 denormalized number 除以 256，因為這邊為 denormalized number 表示，不會透過操作 E 的部分而是直接將 F 部分右移 8 位。
第`16`行 : r 可以想成一個很小的數字了，他第一個數值為 1 的 bit 會在原本 float F 位置中的的第 8 位，或者 8 位之後。而進位條件就以第一位是否為1來判斷進位。
>[https://engineering.fb.com/ai-research/floating-point-math/](https://engineering.fb.com/ai-research/floating-point-math/) 提到的例子
>**Keys to more efficient floating point**
>3. General floating point machinery: This handles the “floating” of the radix point and is thus integral to a floating point representation. Examples are leading zero (LZ) counters for renormalization, shifters for significand alignment, and rounding logic. Floating point precision also dominates the hardware resources used for this machinery.
```c=17
*py &= 0xffff0000;
return y;
}
```
最後加上 mask 使得輸出符合 bfloat16 型態，為輸出答案。
### 執行結果
```
3.140625=40490000
3.140625=40490000
1.200000=3f99999a
1.203125=3f9a0000
2.310000=4013d70a
2.312500=40140000
3.460000=405d70a4
3.453125=405d0000
5.630000=40b428f6
5.625000=40b40000
```
### 延伸問題
1. 改進上述程式碼，實作 DP/SP 轉換程式，並針對 BFloat16 撰寫測試程式，應儘量涵蓋有效的數值輸入和輸出範圍
2. 考慮批次轉換 FP32/FP64 為 BFloat16 的需求，請改進上述程式碼，得以提高轉換的效率
---
## 測驗二 [ring buffer](https://en.wikipedia.org/wiki/Circular_buffer) 實作
### 巨集程式碼解釋 :
`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)
```
當要對 buffer 寫入一個新的值的時候，期望流程 :
**寫入前**
```graphviz
digraph D {
node_B [shape=record label="{}|{<s> A}|{B}|{C}|{<e>}|{}|{}|{}"];
START ->node_B:s
END ->node_B:e
}
```
**寫入後**
```graphviz
digraph D {
node_B [shape=record label="{}|{<s> A}|{B}|{C}|{D}|{<e>}|{}|{}"];
START ->node_B:s
END ->node_B:e
}
```
可以拆成兩個步驟 :
1. 將值寫在 END 指向位置
2. END 往後移動 1 格
`ringbuf_write_peek(BUF)`
peek 一詞可以想成瞥一眼，看一下 END 是什麼卻不 pop 出來。
由於此架構中 END 一定是指向空的，其實這裡想成為了在該位置填值就可以了，也就是上面的第一步驟。
`ringbuf_write_skip(BUF)`
可以想成上面第二步驟，要注意當 buffer 是空的情形，移動 END 之外還要考慮 START。
```c=21
#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)
```
當要對 buffer 讀出一個新的值的時候，期望流程 :
**讀出前**
```graphviz
digraph D {
node_B [shape=record label="{}|{<s> A}|{B}|{C}|{<e>}|{}|{}|{}"];
START ->node_B:s
END ->node_B:e
}
```
**讀出後**
```graphviz
digraph D {
node_B [shape=record label="{}|{ }|{<s> B}|{C}|{<e>}|{}|{}|{}"];
START ->node_B:s
END ->node_B:e
}
```
可以拆成兩個步驟 :
1. 讀出 START 該值
2. START 往後移動 1 格
`ringbuf_read_peek(BUF)`
看一下當下 START 指向的值，也就是上面第一步驟。
`ringbuf_read_skip(BUF)`
移動 START 至下一格，也就是上面第二步驟。
>值得注意的是 buffer 內的值沒有而且不用清空，透過 START, END 就可以知道內部資料。
```c=28
#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);
```
`ringbuf_write` `ringbuf_read`
這裡就只是上面講的實作部分
:::danger
在沒有 if/else 的巨集中會存在 dangling else 問題嗎 ?
就算巨集中會使用到含 if/else 巨集，那只要在上層做 do{...}while(0) 就可以避免這個問題了。
我覺得這裡的 do{...}while(0) 是多餘的。
> 以下的 `ringbuf_write_peek` 和 `ringbuf_read_peek` 有機會單獨使用，而非透過 `ringbuf_write` 和 `ringbuf_read` 來呼叫。請你思考什麼情境會用ㄉ
:::
:::info
感謝老師提點
為什麼這邊會使用 do{...}while(0) 原因很簡單
在 API 很多很複雜時，難免不小心把巨集誤認為函式，但是其實這件事情本身不嚴重，嚴重的是如果程式碼寫成 :
```c=
#define func(x) \
x>=1; \
x<=1;
/*do something*/
if(k >16)
func(x)
/*do something*/
```
這就會出錯了，該判斷只會執行第一行 `x>=1;` 造成錯誤，而且這種錯誤還挺難找的。
正確而言應該寫成下方樣子
```c=
#define func(x) \
do { \
x>=1; \
x<=1; \
} while (0)
/*do something*/
if(k >16)
func(x)
/*do something*/
```
我覺得其實兩行以上的聚集安全起見都要有 do{...}while(0)
:::
```c=30
#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;
}
```
### 延伸問題
>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 實作
```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;
}
```
### 程式碼解釋
觀察較為簡單理解的版本
```c=
struct llist {
int val;
struct llist *next;
};
int main(){
struct llist *ptr,*ptr2;
ptr = (struct llist[]){9,NULL};
ptr2 = (struct llist[]){8,ptr};
printf("num = %d\n",ptr2->val);
printf("num = %d\n",ptr2->next->val);
return 0;
}
```
上述程式碼可以完成簡單的 list。
~~第`8`行中， 先將 `{9,NULL}` 強制轉為 struct llist 陣列型態，並將這個指標指派給 `ptr`。~~
~~這個行為與 2020q3 Homework2 (quiz2)Q5 延伸問題 想法相似。~~
:::success
*規格書有特別說不是這樣*
>C11規格書 (ISO/IEC 9899:201x) 中
>6.5.2.5 **Compound literals**
Constraints
A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal.
It provides an unnamed object whose value is given by the initializer list. 99)
>99) Note that this differs from a cast expression. For example, a cast specifies a conversion to scalar types or void only, and the result of a cast expression is not an lvalue.
與轉型態無關，這邊是會先指派給 lvalue。
:::
如果將第 `8` 行改寫成為 `ptr = (struct llist*){9,NULL};` 在程式執行時期可能發生錯誤，為 undefined behavior。
第`9`行中，會將 ptr 指派給 next ，進而達到可靜態初始化 link list 行為。
>C11規格書 (ISO/IEC 9899:201x) 中
>**6.5.2.5 Compound literals**
Constraints
>8. EXAMPLE 1
>The file scope definition
`int *p = (int []){2, 4};`
initializes p to point to the first element of an array of two ints, the first having the value two and the
second, four.
The expressions in this compound literal are required to be constant. The unnamed objecthas static storage duration.
釐清觀點回到原本的程式碼 :
第`39`行中
`struct llist *list = cons(cons(cons(cons(NULL, 7), 4), 5), 9);`
`cons(NULL, 7)` 會成為 lvalue 並且指派給外層 cons() 達成在 stack空間的 link list。
在初始化階段可以完成，可能讓程式在執行時間下降，並且不像`malloc()`會額外分配空間。
```c=12
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;
}
```
sorted_insert 為給定一個已經排序過後的 link list(或者空的)，讓給定的 node 加入在正確排序位置上。
第`14`行主要用在當 link list 為空 以及當該 node 需要放置在第一個位置(Head)的情況。
參照 quiz1 即可。
第`26`行 `void sort(struct llist **head)` 則透過將每個 node 進行 `sorted_insert` 達到 insert sort。
### 延伸問題
1. 研讀 [Doubly Linked Lists in C](http://locklessinc.com/articles/dlist/) 並比對 Linux 核心的 linked list 實作予以解說
2. 練習 [LeetCode 148. Sort List](https://leetcode.com/problems/sort-list/)，嘗試將 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 的手法引入到 C 程式中實作
---
## 測驗四 LeetCode 287. Find the Duplicate Number
[LeetCode 287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)給定一個整數序列，其中會有一個數值重複，請找出。
已知條件：
1. 假設陣列長度為 n，數值的範圍是 1 到 n−1
2. 重複的數值不一定只重複一次
```c=
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. 考慮 1,2,3,4,5,6 :
| 十進位 | 二進位 |
| ------ |:------:|
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| TOTAL | 333 |
2. 當存在一個多餘的數字，這裡假設多增加數字為 5
| 十進位 | 二進位 |
| ------ |:------:|
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 5 | 101 |
| TOTAL | 434 |
3. 透過觀察上下兩者 TOTAL bit，我們可以得知 bit 1 與 bit 3 會大於上面尚未加入的情況。而對於每個 bit 而言，若大於上述情況該 bit 設為 1。
以上述例子而言會得到 101 ，而該值就是多餘的數字 5。
4. 觀察另一個例子，我們加入 1 :
比較原先 333 以及後者 334 ，我們可以得到 001，也就是 1。
| 十進位 | 二進位 |
| ------ |:------:|
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 1 | 001 |
| TOTAL | 334 |
5. 以上為每個值重複一次的情況，如果重複的值超過 2 ，則代表原本有個值被代為重複的值，考慮 1,5,3,4,5,6,5 :
原先 333 而後來得到 525 ，我們會觀察到中間值(第 2 bit )少 1 (3 -> 2) ，而第 3 個 bit 以及第 1 個 bit 比原先多 1 。
我們原先考慮大於的 bit 也就是 (101) ，也就是我們預期答案。
| 十進位 | 二進位 |
| ------ |:------:|
| 1 | 001 |
| 5 | 101 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 5 | 101 |
| TOTAL | 525 |
6. 再考慮多取代一個數字為 5
我們也會得到相同結果 比較 (333) (625) 比較大小可以得 5(101)
| 十進位 | 二進位 |
| ------ |:------:|
| 5 | 101 |
| 5 | 101 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 5 | 101 |
| TOTAL | 625 |
### 程式解釋
第`4`行 : `const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);`
${2^{log_2}}$ 該值 >= numsSize，用以表示個別之nums。
第`5`行 : `for (size_t i = 0; i < log_2; i++) {`
用以分別判斷每個 bit 的值，`log_2`可以確保不需要用判斷到多餘的值。
第`8`行 : `for (size_t k = 0; k < numsSize; k++) {`
用以統計第 i 個 bit 的數量
c1 代表原先 bit 的統計值
c2 代表後來更改後的 bit 統計值
```c=14
if (c1 < c2)
res += bit;
```
代表該結果 bit 為 1。
第`6`行中會對每一輪 bit 進行位移。
### 延伸問題
1. 實作不同的程式碼 (合法的 C 程式，可運用 GNU extension)，使其表現優於上述程式碼
查表法 :
```c=
int findDuplicate(int *nums, int numsSize)
{
int * intarray = calloc(numsSize+1,sizeof(int));
for(int i=0;i<numsSize;i++){
if(!intarray[nums[i]])
intarray[nums[i]]=1;
else if(intarray[nums[i]])
return nums[i];
}
return 0;
}
```
可以用更省空間的方式寫 :
//TODO
Sign in with Wallet
Connect another wallet