# 2021q1 Homework3 (quiz3) contributed by <`fwfly`> ## OFF (D) xs_data 在做的事情是抽象化字串的處理． 對於使用者只有看到 xs_data return 的字串， 而不用知道這個字串是原先是屬於哪種類型． 而跟 OFF 有關的程式碼是處理，如果字串屬於大型字串的情形 ```cpp if (xs_is_large_string(x)) return (char *) (x->ptr + OFF); ``` OFF 答案是 **(d) 4** 主要是回答這個在題目中的問題 :::info 「長字串」做 CoW 時，也有 reference counting，那 counter 要存哪裡？ ::: 實作的儲存 reference count 的部分在這裡 ```cpp /* 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 回傳的值，透過以下程式碼可以知道，這是在計算字串佔用的空間 ```cpp x->capacity = ilog2(len) + 1; ``` 以下程式碼註解也指出，capacity 的運算式用 2 的冪 ```cpp /* capacity is always a power of 2 (unsigned)-1 */ capacity : 6; ``` 冪是透過 bit 來計算，所以透過以下程式就可以得到 2 的冪 ```cpp 32 - __builtin_clz(n) ``` 得到以下結果 ```cpp 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 ```cpp /* lowerbound (floor log2) */ static inline int ilog2(uint32_t n) { return LLL; } ``` 結果就會如下，這個結果會比較貼近冪結果 ```c= 4 -> 3-1 = 2 5 -> 3-1 = 2 6 -> 3-1 = 2 7 -> 3-1 = 2 8 -> 4-1 = 3 ``` 因此答案會是 ```cpp 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 (包含結束字元) ```cpp 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 會依照這個條件去刪除字串頭尾有跟條件相同的部分 最簡單的方法就是用兩個迴圈去做比對 ```c= for 從字串第一個字元跑到不是想要跟條件不同的字元 for 逐一比對條件 ``` 如果單純使用兩個迴圈時間複雜度是會到 O(n平方)，尤其是條件越多的時候運算時間會越久． 而題目裡面的程式會了降低時間複雜度，所以採用 `查表` 的方式來達到 O(n) 的效果 (因為查表的時間複雜度為常數, 所以只需要計算迴圈的複雜度) ```c= for 從字串第一個字元跑到不是想要跟條件不同的字元 // O(N) 查表 -> 確認字串是否符合條件 // O(1) ``` ### 如何建立 table 根據 [ISO 8859-1 (Latin-1)](https://cs.stanford.edu/people/miles/iso8859.html) 包含 extend 的部分，全部總共 256 種字體． 題目的程式則是用一個 unit_8 大小 32 的 array 去表示全部的字元． 然後以 8 個為一組，大概就如以下表示 ```cpp | --------|--------|--------| |--------| | 00000000|00000000|00000000|........|00000000| | --------|--------|--------| |--------| ``` 其中每一個 bit 就對應到相對應的字體，例如大寫 ABCD.... ```cpp // 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 ``` 用結構圖來看就會是這樣 ```cpp @ABCDEFG HIJKLM.... | --------|.....|--------|--------| |--------| | 00000000|.....|00000000|00000000|........|00000000| | --------|.....|--------|--------| |--------| ``` 所以假設使用者要濾掉的是 ABH 就會產生以下結果 ```cpp @ABCDEFG HIJKLM.... | --------|.....|--------|--------| |--------| | 00000000|.....|01100000|10000000|........|00000000| | --------|.....|--------|--------| |--------| ``` 可以看到把 ABH 的 bit 設定成 1 ，就可以把查表建立好了 而要判斷字元是不是需要被處理也只要直接從表格中確認 bit 是否為 1 就好 不論是設定或者是查表，都要做找 bit 這個動作．要找的有兩個 1. index 是多少 2. 哪個 bit 從上圖可以看到透過`除以 8` 可以得到 index，所以程式碼如下 ```cpp mask[(uint8_t) byte / 8] ``` 再來是哪個 bit, 從上圖可以知道 `mod 8` 可以找到 bit ```cpp byte % 8 ``` 但是這樣只是知道是第幾個 bit 並沒有辦法真的去設定或查表． 所以透過 `shift` 的方式則處理想要的 bit ```c 1 << (uint_8) byte%8 ``` 最後如果是設定，可以用`對 1 做 or`把想要的 bit 設定成 1 所以 SSS 的答案則會如下 ```cpp mask[(uint8_t) byte / 8] |= 1 << (uint_8) byte%8 ``` 而 CCC 因為是在做查表的動作，所以是`對 1 做 &` ```cpp mask[(uint8_t) byte / 8] & 1 << (uint_8) byte%8 ```