# 2020q1 Homework2 (quiz2)
contributed by < [simpson0114](https://github.com/simpson0114/quiz2) >
###### tags: `linux2020`

## 測試環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.4 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic

$ cat /proc/version
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

## 作業要求
- [x]重新回答第 2 周測驗題
- [ ]解釋上述程式碼運作原理，並提出改進方案，可善用 GDB 追蹤和分析
- [ ]以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 和類似 strtok 功能的函式實作
- [ ]設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference
- [ ]在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說

## 測驗題分析
### 第一題
本題所在位置為 `xs.c:xs_new` 函式中

xs *xs_new(xs *x, const void *p)
{
    *x = xs_literal_empty();
    size_t len = strlen(p) + 1;
    if (len > AAA) {
        x->capacity = ilog2(len) + 1;
        x->size = len - 1;
        x->is_ptr = true;
        x->ptr = malloc((size_t) 1 << x->capacity);
        memcpy(x->ptr, p, len);
    } else {
        memcpy(x->data, p, len);
        x->space_left = 15 - (len - 1);
    }
    return x;
}

這個函式用途為初始化 `xs` 結構的設定，因此可以先觀察 `xs` 的結構

typedef union {
    /* allow strings up to 15 bytes to stay on the stack
     * use the last byte as a null terminator and to store flags
     */
    char data[16];

    struct {
        uint8_t filler[15],
            /* how many free bytes in this stack allocated string
             * same idea as fbstring
             */
            space_left : 4,
            /* if it is on heap, set to 1 */
            is_ptr : 1, flag1 : 1, flag2 : 1, flag3 : 1;
    };

    /* heap allocated */
    struct {
        char *ptr;
        /* supports strings up to 2^54 - 1 bytes */
        size_t size : 54,
            /* capacity is always a power of 2 (unsigned)-1 */
            capacity : 6;
        /* the last 4 bits are important flags */
    };
} xs;

因此我們可以知道 `len` 所代表的就是 `p` 的字元數，而由結構可以看到`data` 的陣列大小為16，因此就可以判斷 `AAA` 的答案為16。

### 第二題、第三題
此兩題所在位置為 `xs.c:xs_trim` 函式中

xs *xs_trim(xs *x, const char *trimset)
{
    if (!trimset[0])
        return x;

    char *dataptr = xs_data(x), *orig = dataptr;

    /* similar to strspn/strpbrk but it operates on binary data */
    uint8_t mask[BBB] = {0};
    
#define check_bit(byte) (mask[(uint8_t) byte / 8] CCC 1 << (uint8_t) byte % 8)
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

    size_t i, slen = xs_size(x), trimlen = strlen(trimset);

    for (i = 0; i < trimlen; i++)
        set_bit(trimset[i]);
    for (i = 0; i < slen; i++)
        if (!check_bit(dataptr[i]))
            break;
    for (; slen > 0; slen--)
        if (!check_bit(dataptr[slen - 1]))
            break;

觀察 `set_bit(byte)` 這個函式主要的功能是將字元的數值放進 `mask` 裡面的一個位元中，所以考慮所有字元都能存入 $256 / 8 = 32$ ，因此 BBB 為 $32$。
而根據 `check_bit(byte)` 的用途，可以得知他是要確認字元是否該修剪，所以運算後應該得到的數值是
- 非 `0` : 該字元是 `trimset` 中所出現的字元
- `0` : 該字元不是 `trimset` 中所出現的字元

而因為該字元所對應到 `mask` 的位置就是 `1 << (uint8_t) byte % 8)` 的位置，所以 CCC 的答案應該是 `&`。