# 2020q1 Homework3 (quiz4)
contributed by < `Hsuhaoxiang` >
> [第 4 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz4)
## 測驗 `1`
### 程式運作原理
* 程式的 prototype
* `bitcpy` 這個函式在進行位元的 copy
* `_dest` 欲寫入的 buffer 的 address
* `_write` 開始寫入的 offset
* `_src` 要讀取的 buffer 的 address
* `_read` 開始讀取的 offset
* `_count` 讀取多少個位元
```cpp
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t _count)
```
---
* 讀取 _src buffer data
* 在 while 迴圈中做了兩件事:
* 1.讀取 `_src` 中的位元
* 2.寫入 `_dest`
* 因為 `data` 這個變數宣告成 `uint8_t` 只有8個 bits 所以 `bitsize` 不能直接設成 `_count` 大於8個 bits 就必須等到下一次 `while` 才能讀取及寫入，也間接回答出 ==KK2== 為 `bitsize` ( `_count -= bitsize` )
* 接著要從第 `_read + 1` 個 bit 開始讀取資料所以要先向左位移 `read_lhs`
* read_lhs 為 `_read & 7` 為什麼是 7 ？ 因為要只需要左移0～7個 bits ，也可以看成是在做 mod8 ( _read %= 8)運算 ，如果 `_read` 這個 offset 大於7那我們要讀取的地方將會是 `*_src + (_read /8)` 然後從這個byte 開始，與 `write_lhs` 相似我們要寫入的地方也會是 `write_lhs = _write & 7` ，==KK1== 為 7。
* `read_rhs = 8 - read_lhs` 代表的這個 byte 還剩幾個 bits 可以讀取，因為前面已經經過 left shift 所以右邊會自動補零，只有 `read_lhs` 個 bits 是我們能讀的
* `if (bitsize > read_rhs)` 這個判斷在於如果需要取的 bits 數超過 `read_rhs` ，就必須讀取到下個 byte 的資料。
* 因為在`source` 將資料寫入 `data` 後已經經過 source++的處理已經是下個 byte 的資料，所以只要將他向右位移 `read_rhs` 再與 `data` 做 `or` 就能把下個 byte 的資料接在目前讀取的 data 後面
* 最後資料我們都將資料處理好了所以只要根據我們需要讀取的 bits 數找到對應的 mask 就能只讀出我們需要的 bits 。
```cpp
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
```
---
* 寫入 _dest buffer
* `if (write_lhs > 0)` 看懂上面的code之後，可以猜想出這個判斷式就是看須不需要調整寫入 buffer 的位址，如果 `write_lhs` 為零的話自然不需要左右移
* `mask = read_mask[write_lhs]` 不需要寫入的方必須維持原來的值因此 從第0個 bit 到第 `write_lhs` 就需要靠 `read_mask` 將他們以外的 bit 清成0，再來需要將 `data` 寫入第 `write_lhs+1` 把 `data` 向右位移在與前面處理好的 `original & mask` 做 or 運算就能把最終要寫入這個 byte 的資料接在一起，如果要寫入的 bits 數大於這個 byte 中需要被寫入的 bits 數那要將 `data` 剩下的 bits 寫到下個 byte 用的手法也跟上面差不多，只是 mask 改成使用 `write_mask[bitsize - write_rhs]` 因為要寫入的 bit 是從前面開始寫入必須清成零，而後面維持原來的值
:::danger
* `if ((bitsize - write_lhs) > 0)` 這邊我覺得很奇怪，看下面所做的處理應該是要將 `write_rhs`後面幾個 bit 維持原來的值是用在只寫入 buffer 中間個 bit 時頭尾都應該保留原來的值，所以我覺得判斷式應該要改成 `write_rhs > bitsize` ， `write_mask[8-(write_rhs - bitsize)]`
:::
> 程式碼是給你修改，不是拿來背誦的，路見不平，拿 patch 出來！
> :notes: jserv
>==有修改過，還有測試過別的case，原本的因為 input 都是1 output 都是0所以看不出來。==
```cpp
original = *dest;
if (write_lhs > 0) {
mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
if (bitsize < write_rhs)
mask = mask | write_mask[8 - (write_rhs - bitsize)];
*dest++ = (original & mask) | (data >> write_lhs);
}
} else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
*dest++ = data;
}
```
:::success
延伸問題:
1. 解釋上述程式運作的原理，改寫為更精簡且等效的程式碼;
2. 考慮到 alignment 和 word size，改寫為執行效率更高的程式碼;
3. 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境;
> 提示: 觀察 [linux/bitops.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/bitops.h) 裡頭巨集在原始程式碼的運用狀況
:::
---
## 測驗 `2`
### 程式運作原理
* `STRUCT_BODY(type)` 與 [quiz2](https://hackmd.io/@Hsuhaoxiang/quiz2) 對於儲存長字串的手法相似，只不過改成能用不同的資料型態，所以有一個 `type` 參數
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1,\
flag3 : 1; \
type *ptr; \
}
```
* `NEXT_POWER_OF_2(s)` 這邊的 s 是 vector 的 `size` 從名字可以看出是找大於等於 `s` 的2的冪次，目的是為了記憶體的對齊，例如 `s = 3` 的話就該回傳4，還利用了第二次作業學到的硬體指令 `__builtin_clzl` (count leading zero unsigned long) 找出第一個非零 bit 前面有幾個零，再讓1往左 shift `64-clz(s)` ，例如 3 = 0b11 前面有62個零需要向左 shift 2 個 bits 變成 0b100 回傳4，而 `(s & (s - 1)) == 0` 在 `s` 是二的冪次方時會成立，例如16 = 0b10000 ，15 = 0b01111 ， 15&16 == 0，==VV1 = (s & (s - 1)) == 0==。
```cpp
#define NEXT_POWER_OF_2(s) \
(s & (s - 1)) == 0 \
? s \
: (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */
```
* v(t, s, name,...) 這個 macro 裡面也用了 [quiz2](https://hackmd.io/@Hsuhaoxiang/quiz2) 中 union 的手法， 而 name 為宣告的 vector 名稱後面接的 `__attribute__((cleanup(vec_free)))` 就是當變數離開他的 scope 時會自動呼叫 `vec_free` 這個自己定義的函示， `__attribute__` 是 GCC extension 可以參考[你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick)，`{.buf = {__VA_ARGS__}}`則是在初始化 vector 中的成員，其中 `{__VA_ARGS__}` 就是一開始 `name` 後面的 `...`，可以是複數個參數。
* `name.size` 這邊是計算 vector 中有多少元素， `__VA_ARGS__` 就是存入 vector 的元素，但為什麼要加上0然後最後再減掉1 ？ 原本想說是宣告空的 vector 時才不會出問題，但實際改了之後發現還是能順利的算出現在 vector 中有的元素個數，還要再想想為什麼要這樣算。
* `sizeof((__typeof__(name.buf[0])[]){__VA_ARGS__}) / sizeof(name.buf[0]);`
* `name.capacity` 是實際分配出的記憶體大小，算出整個 array 大小再除以一個元素大小就能得到了，也可以初始化為 `NEXT_POWER_OF_2(s)`
:::warning
main()
{
v(int, 0, vec3);
printf("vec3 size:%zu\n",vec3.size);
return 0;
}
輸出：vec3 size:0
:::
```cpp
#define v(t, s, name,...) \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - 1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
```
* `__vec_reserve` 確保 vector 有 `n` 以上的 `capacity` 如果不夠則使用 `relloc` 或是 `malloc` 分配記憶體。
```cpp
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
```
* `__vec_push_back` 中我看最久才看懂的地方是 `&v->ptr[v->size++ * elemsize]`為何要乘上 `elemsize` ？因為一開始就將 `v` 的 `STRUCT_BODY` 的資料型別用 `char` 只佔1 byte，所以再乘上 `elemsize` 才是正確的記憶體位置。
```cpp
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
```
* `#define vec_pop_back(v) (void) (VV2)`
* 有兩個選項看 function 名稱可以知道將元素從 vector 移除，因為size 是目前元素個數只要將 size 減一 ， push 時就會從目前 `size+1` 開始，看起來就是從vector最後一個元素加入元素一樣，事實上元素沒有移除掉，所以 ==VV2 = v.size -= 1==
* `vec_pop_back(v)` 沒有先確認目前 vector 的 size 所以當一個空的 vector pop 時會出問題。
```cpp
#define vec_pop_back(v) \
if(v.size>0) (v.size -= 1); \
else fprintf( stderr, "warning! vector is empty\n")
```
### 效率分析
:::success
延伸問題:
1. 解釋上述程式運作的原理，比照 [quiz2](https://hackmd.io/@sysprog/BJXNYx5NL) 進行效率分析;
2. 指出上述實作的限制並提出改進方案;
3. 參照 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 文件和對應原始程式碼，以上述程式為基礎，實作 vector 經典操作
:::
Sign in with Wallet
Connect another wallet