Try   HackMD

2020q1 Homework3 (quiz4)

contributed by < kylekylehaha >

第四週測驗
作業要求

tags: linux2020

測驗一

題目解析

在解題之前,必須先瞭解各個變數的用意:

  • *_dest: 寫入的目標起始位置
  • _write: 寫入的位移量
  • *_src: 讀取的目標起始位置
  • _read: 讀取的位移量
  • _count: 欲複製的 bits 個數

KK1

  • 由於 bitcpy 不一定是從第一項開始,因此必須計算偏移量。其中 read_lhsdata 須向左偏移的量,故我們用 bitwise 操作: _read & 7 來做到 _read % 8 的效果。當我們需要 mod
    2n
    時,我們只需和
    2n1
    做 AND 運算即可。
  • white_lhs 也是同樣道理,故本題答案為:

KK1 = 7

KK2

  • 由於我們已知 _count 為欲複製的 bits 個數,其中在 while 內每次最多 bitsize 做複製,故可以得知每當 while 結束時,欲複製的 bits 數會減少 bitsize 個。故本題答案為:

KK2 = bitsize

程式碼運作原理

...
    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 運算。
if (bitsize < 8)
    data &= read_mask[bitsize];
  • 如果 bitsize 小於 8 時,須將多餘的部分,用 mask 做消除。
  • 做到此時,已確定 data 為這次 while 內要複製的位元。

寫入分為兩種 case:

  1. white_lhs > 0: 需要調整寫入的位置。
  2. white_lhs == 0: 直接將 data 寫入 *dest 即可。

我們先討論 case2

...
 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,其中又分為兩種情況:

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(代表欲寫入的資料跨過一個位元組。)

*dest++ = (original & mask) | (data >> write_lhs)
  • original & mask: 用來保留原本的部分,避免被污染。
  • data >> write_lhs: 將 data 右移到正確的位置,來避免污染原本的資料。
  • 兩者做 OR 運算後為正確寫入該 *dest 的資料。
original = *dest & write_mask[bitsize - write_rhs];
  • 由於上一行 *dest++,故此時 *dest 為下一項的值。
  • write_mask[bitsize - write_rhs 為欲保留的部分
  • 故兩者做 AND 運算即可得正確欲保留的部分。
*dest = original | (data << write_rhs)
  • data << write_rhs: 將欲寫入的部分左移到正確位置。
  • original 做 OR 運算,即為正確寫入的資料。

bitsize <= write_rhs

  • 看是否需要更新 mask,如果不需更新則直接寫入 *dest
  • 如果須更新,則更新 mask 來保留正確的 original 部分。

_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))
    s

vv1 = s & (s-1) == 0

VV2

  • 由名字可以判斷,此為 pop stack 內的 element,故必須將 vector 內的個數 - 1。
  • 其中, size 為 vector 內的個數, capacity 為 vector 內的最大容量,故我們可以知道答案為:

vv2 = v.size -= 1

程式碼運作原理

#define STRUCT_BODY(type)                                                 \
    struct {                                                              \
        size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1,\
            flag3 : 1;                                                    \
        type *ptr;                                                        \
    }
  • 在這次的題目的 macro ,出現了quiz2 提到的 folly:fbstring: 當字串長度太大時,用 heap,反之則用 stack 來儲存。
#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
  • __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}};
    • __VA_ARGS__ 的內容存入 buf。
    • 當被形容的變數離開時,會呼叫 vec_free來釋放記憶體。

延伸問題

效率分析

實作 vector 經典操作

參考資料