# 2023q1 Homework2 (quiz2) contributed by < `koty6069` > [2023q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz2) ## 測驗 `1` ### 程式碼解析 原文有提到我們可改動原本數值 `x` ，從其原本有數值的最高位元至最低位元皆設成 `1` 。 >最初 x 是 0010000000000000，經過一系列操作後，成為 0011111111111111，亦即設定 (set，即指派為 1) 自原本最高位元到最低位元中，所有的位元。 因此程式碼除了 `return CCCC` 以外，皆是在做設定為 `1` 的動作。 我們可以上面引文之數值 `0010000000000000` 進行操作，觀察其結果。 ```c x |= x >> 1; //0011000000000000 x |= x >> 1; //0011100000000000 x |= x >> 1; //0011110000000000 x |= x >> 1; //0011111000000000 x |= x >> 1; //0011111100000000 x |= x >> 1; //0011111110000000 x |= x >> 1; //0011111111000000 ``` 以上進行了七次 `x |= x >> 1`，將最高位的 `1` 其右方七個位元都設成 `1` ，也就是目前從原先的最高位 `1` 開始有連續 8 個位元為 `1` ，接下來可直接 shift 8 個位元，再將右方 8 個位元皆設成 `1` ，後續再 shift 16 及 32 個位元，即可將全部 64 個位元皆覆蓋到，因此 `AAAA` 為 `8` ， `BBBB` 為 `32`。 ```c x |= x >> 8; x |= x >> 16; x |= x >> 32; ``` 只要將上述連續的 `1` 再加上 `1` 即可得到 「最接近且大於等於的 2 的冪的值」，因此最後的 `CCCC` 為 `x + 1` 。 ```c return x + 1; ``` ### 使用 `__builtin_clzl` 改寫 `__builtin_clzl` 會回傳最高位的 `1` 之前 0 的數量，使用 64 減去此值會得到最高位的 `1` 所在位置，因此將 1 向左移動此數值（`64 - shift`）就能得到「最接近且大於等於的 2 的冪的值」。 ```c uint64_t next_pow2(uint64_t x) { int shift = __builtin_clzl(x); return 1UL << (64 - shift); } ``` ### 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？ 可確認到 `bsrq` 指令。 ``` next_pow2: .LFB13: .cfi_startproc endbr64 bsrq %rdi, %rdi movl $64, %ecx movl $1, %eax xorq $63, %rdi subl %edi, %ecx salq %cl, %rax ret .cfi_endproc ``` ## 測驗 `2` ### 程式碼解析 根據註解，每次迴圈會將最右方的 `1` 移除，若移除後數值為 0 ，代表此數為 2 的冪，此時需要將長度增加，原因是二進位制在遇到 2 的冪時會使得紀錄需要的位元數增加。 >舉例來說，3 的二進位為 `11` ，需要兩個位元作紀錄， 4 的二進位則為 `100` 需要三個位元。 因此 `if` 需要在移除 `1` 後數值為 0 的情況下將 `len` 增加，`DDDD` 為 `i & (i - 1)`，將 `i` 減一時會與最右方的 `1` 做借位，接著進行 `&` 操作會將剛剛操作後產生的 `1` 和原本最右方的 `1` 都消除，此時若數值為 0 則代表此數為 2 的冪。 ```c if (!(i & (i - 1))) len++; ``` 答案需要我們將二進制全部串接，每次迴圈需要將二進制的 `i` 串接到目前的答案尾端，因此我們需要將目前的答案向左 shift ，再透過 `&` 操作將 `i` 串接上去， `EEEE` 為 `ans << len` 。 ```c ans = (i | (ans << len)) % M; ``` ## 測驗 `3` ### 程式碼解析 由於後續使用迴圈一次處理 8 bytes （一個位元組），所以一開始先透過 `len >> 3` （也就是 `len / 8`）來計算總共有多少位元組。 ```c const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + len >> 3; ``` 迴圈即是使用 SWAR 一次檢測一個位元組，也就是原文有解釋過的 `not bit6 and bit7` 操作，並使用 `count` 紀錄有幾個 byte 符合 `10xx.xxxx` 的形式（也就是有多少 `continuation byte`）。 ```c size_t count = 0; for (; qword != end; qword++) { const uint64_t t0 = *qword; const uint64_t t1 = ~t0; const uint64_t t2 = t1 & 0x04040404040404040llu; const uint64_t t3 = t2 + t2; const uint64_t t4 = t0 & t3; count += __builtin_popcountll(t4); } ``` 得到 `continuation byte` 的數量後，根據原文說明，需要將此數量從總字串長度中減去。 > 若輸入的字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。 這邊先計算整除 8 的部分長度為何，透過 `(1 << 3) * (len / 8)` 將最低位 3 bits 設為 0 ，得到長度後將其減去 `count` ，因此 `AAAA` 為 `3`。 ```c count = (1 << 3) * (len / 8) - count; ``` 最後計算未滿 8 bytes 的部分中有多少 `continuation byte` ，並將其補上。 ```c count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; ``` `len & 7` 可得知未滿 8 bytes 的長度為何，將此長度的字元使用 `count_utf8` 逐字元檢查是否為 `continuation byte` 並加回 `count`，因此 `BBBB` 和 `CCCC` 皆為 `7` ，若剩餘的長度為 0 ，代表不須多做檢測，將 `count` 加上 0 即可，因此 `DDDD` 為 0 。 ## 測驗 `4` ### 程式碼解析 原始程式碼中，每次會將 `x` 向左 shift 一位元，再與 `0x8000` 做 `&` ，用意是檢測當前的 MSB 是否為 1 ，若非 1 則不符合樣式，再對照下方提供的範例樣式，可得知要尋找的樣式為從 MSB 開始有連續位元為 1 的數。 ```c for (; x > 0; x <<= 1) { if (!(x & 0x8000)) //0x8000 => 1000 0000 0000 0000 return false; } ``` ``` pattern: 8000 (32768) => 1000 0000 0000 0000 pattern: c000 (49152) => 1100 0000 0000 0000 pattern: e000 (57344) => 1110 0000 0000 0000 pattern: f000 (61440) => 1111 0000 0000 0000 pattern: f800 (63488) => 1111 1000 0000 0000 pattern: fc00 (64512) => 1111 1100 0000 0000 ``` 後續的改進中，首先可以先觀察將 `x` 取 `-x` 也就是二補數後的結果，我們使用上面的範例來觀察。 ``` c000: 1100 0000 0000 0000 -c000: 0100 0000 0000 0000 ========================== f800: 1111 1000 0000 0000 -f800: 0000 1000 0000 0000 ``` 可發現取 `-x` 後只會保留最右方的 `1` ，這時與原數做 `XOR` 操作，會將原數值中最右的的 `1` 消除，因此符合樣式的值在 `XOR` 後應會比原數值小。 ``` 1100 0000 0000 0000 ^ 0100 0000 0000 0000 ------------------------- 1000 0000 0000 0000 ``` ``` 1111 1000 0000 0000 ^ 0000 1000 0000 0000 ------------------------- 1111 0000 0000 0000 ``` 因此可推測答案 `EEEE` 為 `-x` ， `FFFF` 為 `x` 。 ```c const uint16_t n = -x; return (n ^ x) < x; ``` 我們可再取一不符合樣式的值做檢測，會發現不符合樣式的值在 `XOR` 後會比原數大，因此會返回 `false` 符合上述推測。 ``` d000: 1101 0000 0000 0000 -d000: 0010 0000 0000 0001 ``` ``` 1101 0000 0000 0000 ^ 0010 0000 0000 0001 ------------------------- 1111 0000 0000 0001 ```