2021q1 Homework3 (quiz3)

contributed by <fwfly>

OFF (D)

xs_data 在做的事情是抽象化字串的處理．
對於使用者只有看到 xs_data return 的字串，
而不用知道這個字串是原先是屬於哪種類型．
而跟 OFF 有關的程式碼是處理，如果字串屬於大型字串的情形

    if (xs_is_large_string(x))
        return (char *) (x->ptr + OFF);

OFF 答案是 (d) 4
主要是回答這個在題目中的問題

「長字串」做 CoW 時，也有 reference counting，那 counter 要存哪裡？

實作的儲存 reference count 的部分在這裡

    /* 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_data 讀取大型字串時，需要跳過前面 4 個 bytes 才能拿到真實的字串

LLL (B)

LLL 是在 ilog2 這個 function 回傳的值，透過以下程式碼可以知道，這是在計算字串佔用的空間

x->capacity = ilog2(len) + 1;

以下程式碼註解也指出，capacity 的運算式用 2 的冪

/* capacity is always a power of 2 (unsigned)-1 */
capacity : 6;

冪是透過 bit 來計算，所以透過以下程式就可以得到 2 的冪

32 - __builtin_clz(n)

得到以下結果

4 -> 3 0000 0000 0000 0000 0000 0000 0000 0100
5 -> 3 0000 0000 0000 0000 0000 0000 0000 0101
6 -> 3 0000 0000 0000 0000 0000 0000 0000 0110
7 -> 3 0000 0000 0000 0000 0000 0000 0000 0111
8 -> 4 0000 0000 0000 0000 0000 0000 0000 1000

問題是 4 得 2 的冪應該是 2
5 會是 2.xxxx
6 也會是 2.xxxx
直到 8 才會是 3
因此 4 ~ 8 之間則會介於 2 到 3 之間
所以就如同程式註解裡面說的取 lower bond

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

結果就會如下，這個結果會比較貼近冪結果

4 -> 3-1 = 2
5 -> 3-1 = 2
6 -> 3-1 = 2 
7 -> 3-1 = 2 
8 -> 4-1 = 3 

因此答案會是

32 - __builtin_clz(n) -1

To do

• 5,6,7 的 2 的冪介於 2 ~ 3 之間，取 2 是否會有影響

NNN (A)

NNN 在 xs_new 裡面，這個 function 主要是產生一個新字串的，如同題目提到
主要分兩種

1. 長度 <= 15
2. 長度 > 15

NNN 的部分是在判斷字串是否屬於 大型字串 ( > 15 )
然而在程式碼中 len 的長度是有被 +1 (包含結束字元)

size_t len = strlen(p) + 1;

因為這樣的緣故， NNN 的判斷不會為 15 而是為 16
所以答案是 (a) 16

To do

• 解釋為什麼要包含結束字元

CCC(D) 跟 SSS( C )

在處理 CCC 跟 SSS 之前要先知道 xs_trim
xs_trim 是在做刪除前後指定字元．
使用者可以指定想要消除的字元，然後 xs_trim 會依照這個條件去刪除字串頭尾有跟條件相同的部分

最簡單的方法就是用兩個迴圈去做比對

 for 從字串第一個字元跑到不是想要跟條件不同的字元
    for 逐一比對條件

如果單純使用兩個迴圈時間複雜度是會到 O(n平方)，尤其是條件越多的時候運算時間會越久．

而題目裡面的程式會了降低時間複雜度，所以採用 查表 的方式來達到 O(n) 的效果 (因為查表的時間複雜度為常數, 所以只需要計算迴圈的複雜度)

 for 從字串第一個字元跑到不是想要跟條件不同的字元 // O(N)
    查表 -> 確認字串是否符合條件 // O(1)

如何建立 table

根據 ISO 8859-1 (Latin-1) 包含 extend 的部分，全部總共 256 種字體．
題目的程式則是用一個 unit_8 大小 32 的 array 去表示全部的字元．
然後以 8 個為一組，大概就如以下表示

| --------|--------|--------|        |--------|  
| 00000000|00000000|00000000|........|00000000|
| --------|--------|--------|        |--------| 

其中每一個 bit 就對應到相對應的字體，例如大寫 ABCD…

// A 的 ascii 是 65
A = 65/8 = 8 // array 中 idex 8 的位置
    65%8 = 1 // 第 1 個 bit

// B 的 ascii 是 66
B = 66/8 = 8
    66%8 = 2 // 第 2 個 bit

// C 的 ascii 是 67
C = 67/8 = 8
    67%8 = 3 // 第 3 個 bit
....    
...

// H 的 ascii 是 72
H = 72/8 = 9 // array 中 idex 9 的位置
    72%8 = 0 // 第 0 個 bit

用結構圖來看就會是這樣

                 @ABCDEFG HIJKLM.... 
| --------|.....|--------|--------|        |--------|  
| 00000000|.....|00000000|00000000|........|00000000|
| --------|.....|--------|--------|        |--------| 

所以假設使用者要濾掉的是 ABH 就會產生以下結果

                 @ABCDEFG HIJKLM.... 
| --------|.....|--------|--------|        |--------|  
| 00000000|.....|01100000|10000000|........|00000000|
| --------|.....|--------|--------|        |--------| 

可以看到把 ABH 的 bit 設定成 1 ，就可以把查表建立好了
而要判斷字元是不是需要被處理也只要直接從表格中確認 bit 是否為 1 就好

不論是設定或者是查表，都要做找 bit 這個動作．要找的有兩個

1. index 是多少
2. 哪個 bit

從上圖可以看到透過除以 8 可以得到 index，所以程式碼如下

mask[(uint8_t) byte / 8]

再來是哪個 bit, 從上圖可以知道 mod 8 可以找到 bit

byte % 8 

但是這樣只是知道是第幾個 bit 並沒有辦法真的去設定或查表．
所以透過 shift 的方式則處理想要的 bit

1 << (uint_8) byte%8

最後如果是設定，可以用對 1 做 or把想要的 bit 設定成 1
所以 SSS 的答案則會如下

mask[(uint8_t) byte / 8] |= 1 << (uint_8) byte%8

而 CCC 因為是在做查表的動作，所以是對 1 做 &

mask[(uint8_t) byte / 8] & 1 << (uint_8) byte%8