# 2021q1 Homework3 (quiz3)
contributed by < `mahavishnuj` >

:::danger
注意作業規範：登記在作業區的網址，應為「瀏覽模式」的發表網址。唯有掌握細節，才能挑戰龐大無比的 Linux 核心。
:notes: jserv
:::

## 測驗 `1`

#### OFF = ?

- `(d) 4`

在 `xs_allocate_data` 裡面我們看到說明說 `The extra 4 bytes are used to store the reference count` 我們已知 `ptr` 是指向 `char` 的指標，位移量在這裡是一個 `byte` 的大小，但是要保留四個 `byte` 情況下所以要一次移動四個單位

static void xs_allocate_data(xs *x, size_t len, bool reallocate)
{
    /* Medium string */
    if (len < LARGE_STRING_LEN) {
        x->ptr = reallocate ? realloc(x->ptr, (size_t) 1 << x->capacity)
                            : malloc((size_t) 1 << x->capacity);
        return;
    }

    /* Large string */
    x->is_large_string = 1;

    /* The extra 4 bytes are used to store the reference count */
    x->ptr = reallocate ? realloc(x->ptr, (size_t)(1 << x->capacity) + 4)
                        : malloc((size_t)(1 << x->capacity) + 4);

    xs_set_refcnt(x, 1);
}

#### `LLL = ?`

- `(b) 32 - __builtin_clz(n) - 1`

說明提到是取 `lowerbound` 所以在扣掉第一個遇到 `1` 的地方之後還要在扣掉 `1` ， 以 $log_{2}3$ = 1.584... 取下底則等於 `1` 以`32 bits` 來表示 `3 = 0000 0000 0000 0000 0000 0000 0000 0011` ， `__builtin_clz(3) = 30` ， `32-30 = 2` ，若是要取上高斯則沒問題，但我們是要取下高斯所以必須再減一。

/* lowerbound (floor log2) */
static inline int ilog2(uint32_t n) { return LLL; }

#### `NNN = ?`

- `(a) 16`

`NNN` 用來判斷字串的長度，是否是大字串，因此用大於 `16` 來比較

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

#### `SSS = ?`

- `(c) mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8`

在範例中的程式碼 `xs_trim(&string, "\n ")` 透過 `xc_trim` 把字串中的的空白跟 `\n` 給去除，得到結果為 `[foobarbar] : 9 ` ，我們仔細看 `trim` 如何實作

    xs string = *xs_tmp("  foobarbar  \n\n");
    xs_trim(&string, "\n ");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    xs prefix = *xs_tmp("((("), suffix = *xs_tmp(")))");
    xs_concat(&string, &prefix, &suffix);
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

傳入的除了我們即將修改的 `x` 之外還有要去除的參考值 `trimset` 且內容為 `char` ，每個 `char` 大小為一個 `byte` 即八個 `bits` 再看了同學的解說之後更暸解查表與建表的過程。

:::danger
避免說「看了同學的解說」，只要參照他人成果，都該清楚標註來源。將心比心，你會希望自己的心血被他人一筆帶過嗎？

既然你啟發自他人，那詳讀後應該會有更多想法，寫出來。

「傳入的除了我們即將修改的 `x` 之外還有要去除的參考值 `trimset` 且內容為 `char`」這句話不通順，請改進你的漢語表達！
:notes: jserv
:::

#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

因為一個字元是以一個 `byte` 來儲存，以字元 'A' 來表示， A 的 `ASCII` 碼是 0x41 以八個位元來表示就是 `0100 0001` 因此 `/8` 又可以當作向右做 `bitwise` `>>3` 因此變成 `0000 1000` 以十進位表示就是 8 ， `mask[8] |= 1 << (0100 0001)%8` ， 跟 `8` 取餘數又可以表示成跟 `& 7` ，餘下的結果 `mask[8] |= 1 << 1` ， `mask` 每一個元素又是 `8` 個 `bit` ，運算完後成 `mask[8] = 0000 0010`

:::warning
TODO: 研讀 C 語言規格書，找出關於 `char` 型態實際佔用空間的描述，是否總是 1 byte 呢？
:notes: jserv
:::

#### `CCC = ?`

- `(d) mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8`

define check_bit(byte) (CCC)

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

`check_bit` 由於先前已經用 `set_bit` 來建立一個表，之後透過 `check_bit` 的方式來進行查表， 再以 `A` 作為例子，會得到 `mask[8] |= 1 << 1` 得到 `True` ， 如此的查詢速度可以達到常數時間。

#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)

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

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

    if (xs_cow_lazy_copy(x, &dataptr))
        orig = dataptr;

    /* similar to strspn/strpbrk but it operates on binary data */
    uint8_t mask[32] = {0};

#define check_bit(byte) (CCC)
#define set_bit(byte) (SSS)
    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;
    dataptr += i;
    slen -= i;

    /* reserved space as a buffer on the heap.
     * Do not reallocate immediately. Instead, reuse it as possible.
     * Do not shrink to in place if < 16 bytes.
     */
    memmove(orig, dataptr, slen);
    /* do not dirty memory unless it is needed */
    if (orig[slen])
        orig[slen] = 0;

    if (xs_is_ptr(x))
        x->size = slen;
    else
        x->space_left = 15 - slen;
    return x;
#undef check_bit
#undef set_bit
}

---

## COW and experiment

- to-do