2020q1 Homework3 (quiz4)

contributed by < Hsuhaoxiang >

第 4 週測驗題

測驗 `1`

程式運作原理

程式的 prototype
- bitcpy 這個函式在進行位元的 copy
- _dest 欲寫入的 buffer 的 address
- _write 開始寫入的 offset
- _src 要讀取的 buffer 的 address
- _read 開始讀取的 offset
- _count 讀取多少個位元

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 。

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 是從前面開始寫入必須清成零，而後面維持原來的值

if ((bitsize - write_lhs) > 0) 這邊我覺得很奇怪，看下面所做的處理應該是要將 write_rhs後面幾個 bit 維持原來的值是用在只寫入 buffer 中間個 bit 時頭尾都應該保留原來的值，所以我覺得判斷式應該要改成 write_rhs > bitsize ， write_mask[8-(write_rhs - bitsize)]

程式碼是給你修改，不是拿來背誦的，路見不平，拿 patch 出來！

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv
有修改過，還有測試過別的case，原本的因為 input 都是1 output 都是0所以看不出來。

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;
}

延伸問題:

解釋上述程式運作的原理，改寫為更精簡且等效的程式碼;
考慮到 alignment 和 word size，改寫為執行效率更高的程式碼;
在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境;

提示: 觀察 linux/bitops.h 裡頭巨集在原始程式碼的運用狀況

測驗 `2`

程式運作原理

STRUCT_BODY(type) 與 quiz2 對於儲存長字串的手法相似，只不過改成能用不同的資料型態，所以有一個 type 參數

#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。

#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 中 union 的手法，而 name 為宣告的 vector 名稱後面接的 __attribute__((cleanup(vec_free))) 就是當變數離開他的 scope 時會自動呼叫 vec_free 這個自己定義的函示， __attribute__ 是 GCC extension 可以參考你所不知道的C語言：技巧篇，{.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)

main()
{
    v(int, 0, vec3);
    printf("vec3 size:%zu\n",vec3.size);
    return 0;
}

輸出：vec3 size:0

#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 分配記憶體。

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 才是正確的記憶體位置。

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 時會出問題。

#define vec_pop_back(v)                                \
    if(v.size>0) (v.size -= 1);                        \
    else fprintf( stderr, "warning! vector is empty\n")

效率分析

延伸問題:

解釋上述程式運作的原理，比照 quiz2 進行效率分析;
指出上述實作的限制並提出改進方案;
參照 folly::fbvector 文件和對應原始程式碼，以上述程式為基礎，實作 vector 經典操作

2020q1 Homework3 (quiz4)

測驗 1

程式運作原理

測驗 2

程式運作原理

效率分析

測驗 `1`

測驗 `2`