# 2020q1 Homework3 (quiz4)
contributed by < `kylekylehaha` >
> [第四週測驗](https://hackmd.io/@sysprog/linux2020-quiz4)
> [作業要求](https://hackmd.io/@sysprog/ByJyk6HrL)
###### tags: `linux2020`
## 測驗一
### 題目解析
在解題之前，必須先瞭解各個變數的用意:
* `*_dest`: 寫入的目標起始位置
* `_write`: 寫入的位移量
* `*_src`: 讀取的目標起始位置
* `_read`: 讀取的位移量
* `_count`: 欲複製的 bits 個數
**KK1**
* 由於 bitcpy 不一定是從第一項開始，因此必須計算偏移量。其中 `read_lhs` 為 `data` 須向左偏移的量，故我們用 bitwise 操作: `_read & 7` 來做到 `_read % 8` 的效果。當我們需要 mod $2^n$ 時，我們只需和 $2^n - 1$ 做 AND 運算即可。
* `white_lhs` 也是同樣道理，故本題答案為:
> `KK1` = 7
**KK2**
* 由於我們已知 `_count` 為欲複製的 bits 個數，其中在 while 內每次最多 `bitsize` 做複製，故可以得知每當 while 結束時，欲複製的 bits 數會減少 `bitsize` 個。故本題答案為：
> `KK2` = bitsize
### 程式碼運作原理
```cpp
...
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
...
```
* 由於我們欲複製的位元，並未與位元組對齊，因此我們必須先將 `data` 做調整。由上面 `KK1` 的解析可得知，`read_lhs` 為需向左移的位移量，故必須```data <<= read_lhs ```
* 假如進入條件式 `if (bitsize > read_rhs)`，代表我們要複製的位元在下一項，然而因為第一行的 `data = *source++`，現在 `*source` 已為下一項，故直接將下一項資料向右移 `read_rhs`後，與 `data` 做 OR 運算。
```cpp
if (bitsize < 8)
data &= read_mask[bitsize];
```
* 如果 `bitsize` 小於 8 時，須將多餘的部分，用 mask 做消除。
* 做到此時，已確定 `data` 為這次 while 內要複製的位元。
---
寫入分為兩種 case:
1. `white_lhs` > 0: 需要調整寫入的位置。
2. `white_lhs` == 0: 直接將 `data` 寫入 `*dest` 即可。
我們先討論 case2
```cpp
...
else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
dest++ = data;
}
...
```
* 如果寫入的 `data` 長度小於 8，則必須確保不能污染到原本的資料 `original`，故必須修正 `data`，使 `data` 保留原本的部分以及欲寫入的部分。
* e.g. `bitsize` = 4，代表欲寫入的 `data` 只有前 4 個 bit 是正確的，而 `original & write_mask[bitsize] ` = `original & 00001111b`，即保留後面四個原本的 bit，前面四個為欲修改的 bit。
接著，我們討論 case1，其中又分為兩種情況:
```cpp
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_lhs) > 0)
mask = mask | write_mask[8 - (bitsize - write_lhs)];
*dest++ = (original & mask) | (data >> write_lhs);
}
...
```
`mask` 為用來保留原來資料的部分。
**bitsize > write_rhs**(代表欲寫入的資料跨過一個位元組。)
```cpp
*dest++ = (original & mask) | (data >> write_lhs)
```
* `original & mask`: 用來保留原本的部分，避免被污染。
* `data >> write_lhs`: 將 `data` 右移到正確的位置，來避免污染原本的資料。
* 兩者做 OR 運算後為正確寫入該 `*dest` 的資料。
```cpp
original = *dest & write_mask[bitsize - write_rhs];
```
* 由於上一行 `*dest++`，故此時 `*dest` 為下一項的值。
* `write_mask[bitsize - write_rhs` 為欲保留的部分
* 故兩者做 AND 運算即可得正確欲保留的部分。
```cpp
*dest = original | (data << write_rhs)
```
* `data << write_rhs`: 將欲寫入的部分左移到正確位置。
* 與 `original` 做 OR 運算，即為正確寫入的資料。
**bitsize <= write_rhs**
* 看是否需要更新 `mask`，如果不需更新則直接寫入 `*dest`。
* 如果須更新，則更新 `mask` 來保留正確的 `original` 部分。
---
```cpp
_count -= bitsize;
```
* 更新還剩多少個位元需要被複製。
### 延伸問題
#### 改寫程式碼
## 測驗二
### 題目解析
**VV1**
* 由名字可以知道，此 marco 用來找到給予 `s` ，大於 `s`的最小 2 的次方。
* if `s` 屬於 2 的次方，則 `s` & `s-1` 會等於 `0`，代表 `s` 為 2 的次方。
e.g. s(01000)，s-1(00111) 則`s & (s-1) == 0` ，故回傳 `s`
* if `s` 不屬於 2 的次方，則 `s` & `s-1` 會等於 1，故回傳 `1 << (64 - _builtin_clzl(s))`，其值為:` 2^(64 - _builtin_clz(s))` $\geq$ s
> `vv1` = s & (s-1) == 0
**VV2**
* 由名字可以判斷，此為 pop stack 內的 element，故必須將 vector 內的個數 - 1。
* 其中， `size` 為 vector 內的個數， `capacity` 為 vector 內的最大容量，故我們可以知道答案為：
> `vv2` = v.size -= 1
>
### 程式碼運作原理
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1,\
flag3 : 1; \
type *ptr; \
}
```
* 在這次的題目的 macro ，出現了[quiz2](https://hackmd.io/@sysprog/linux2020-quiz2) 提到的 [folly:fbstring](https://github.com/facebook/folly/blob/master/folly/FBString.h): 當字串長度太大時，用 heap，反之則用 stack 來儲存。
```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])
```
* `__VA_ARGS__` 為 `v(t, s, name, ...)` 中， `...` 的內容，也就是第四項以後的參數。這邊是我第一次看到，故查了一下資料[21世紀C語言之17](https://ithelp.ithome.com.tw/articles/10160393)。
* `__attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}};`
* 將 `__VA_ARGS__` 的內容存入 buf。
* 當被形容的變數離開時，會呼叫 `vec_free`來釋放記憶體。
### 延伸問題
#### 效率分析
#### 實作 vector 經典操作
## 參考資料
* [21世紀C語言之17](https://ithelp.ithome.com.tw/articles/10160393)
* [homework2 (quiz2)](https://hackmd.io/@kylekylehaha/SkTYL62BU)
Sign in with Wallet
Connect another wallet