# 2020q1 Homework3 (quiz4)
contribute by < `simpson0114` >
###### tags: `linux2020`

:::danger
列於 [作業區](https://hackmd.io/@sysprog/linux2020-homework3) 的網址應以發布後的瀏覽模式所得的超連結，請注意規範
:notes: jserv
:::

## 測試環境

NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
Linux version 5.3.0-42-generic (buildd@lcy01-amd64-019) 
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)) 
#34~18.04.1-Ubuntu SMP Fri Feb 28 13:42:26 UTC 2020

## 作業要求
- [ ]重新回答第 4 周測驗題
- [ ]解釋上述程式運作的原理，改寫為更精簡且等效的程式碼
- [ ]考慮到 alignment 和 word size，改寫為執行效率更高的程式碼
- [ ]在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境
- [ ]解釋上述程式運作的原理，比照 quiz2 進行效率分析
- [ ]指出上述實作的限制並提出改進方案
- [ ]參照 folly::fbvector 文件和對應原始程式碼，以上述程式為基礎，實作 vector 經典操作

## 測驗題
### 測驗`1`
此題主要是對於逐 bit 資料複製的讀寫去探討，題目都位於 `bitcpy` 結構中

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)
{
    uint8_t data, original, mask;
    size_t bitsize;
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = _src + (_read / 8);
    size_t write_lhs = _write & KK1;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = _dest + (_write / 8);

...

    while (_count > 0) {
        data = *source++;
        bitsize = (_count > 8) ? 8 : _count;
        
...
        
        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);
            }
        } else {
            if (bitsize < 8)
                data = data | (original & write_mask[bitsize]);
            *dest++ = data;
        }

        _count -= KK2;
    }
}

因為每一次取的起始位置不一定在 byte 的開頭，所以在每一次 read或 write 時都應該檢查並調整使用的位置，而 `write_lhs` 就是為了要將資料湊成一個 byte ，所以要跟 $7$ 去 ＆ 才能知道需要補幾個 bit 的資料，因此 KK1 的答案為：
> KK1 = 7

而在每處理完一筆資料後，就要調整記憶體的位置，但由於處理的資料量 (bitsize) 不一定剛好等於 8 bits ，所以要根據 bitsize 大小去作調整，因此 KK2 的答案為：
> KK2 = bitsize

## 測驗`2`

#define STRUCT_BODY(type)                                                  \
    struct {                                                               \
        size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
            flag3 : 1;                                                     \
        type *ptr;                                                         \
    }

先觀察這個 vector 的結構可以知道 size 代表實際儲存了元素的空間大小;而 capacity 代表這個 vector 擁有的空間。

#define vec_pop_back(v) (void) (VV2)

因為刪除一個 vector 的 element 肯定是減少實際儲存了元素的空間大小，所以 VV2 的答案是：
> VV2 = v.size -= 1