2020q3 Homework2 (quiz2)

contributed by < grb72t3yde >

tags: sysprog2020

---

測驗題目

第二週測驗題

測驗一

目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元:

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

其中 str 是開頭的記憶體地址， size 則是要檢驗的範圍。逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下:

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

---

個人解題思路

1. MMM = ?

1. 首先觀察改寫後之 is_ascii, 我從 line 10 的 while loop condition 以及 payload 的 data type 得知, 這個 while loop 是以 word width 來做是否為 ascii 的判斷。
2. 考慮對於任一 7位元編碼的 ASCII 字元, 其 MSB 必為 0 (其範圍在0~127); 因此, MMM = 0x8080808080808080。
3. 對於不滿一個 word 的 bytes 組, 會在第二個 while loop 對 byte 逐一檢查。

延伸問題

1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？

• 參考提示 你所不知道的 C 語言：記憶體管理、對齊及硬體特性後得知, "編譯器會自動幫我們以 data 的大小做 alignment"; 因此在 is_ascii 函式中之 argument const char str[] 接受的引數以 const char 之寬度對齊
• 如今, 我們想要以 word 的寬度進行 bit-wise operation, 因此使用 memcpy, 將 8個 byte 的資料複製到已宣告且以 uint64_t type 來對齊的變數 payload 中
• 以此達到 "alignment 寬度" 之轉換

思考 : 如果不使用 memcpy?

考慮下列修改 :

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
+   uint64_t *payload = (uint64_t)str;
    while ((i + 8) <= size) {
-       uint64_t payload;
-       memcpy(&payload, str + i, 8);
        if (*payload & MMM)
            return false;
+       payload++;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

使用 gdb 觀察, 仍能達到類似效果; 但是參考 Should I worry about the alignment during pointer casting? 後得知, 這是相較於使用 memcpy() 較危險且不具效率的方法 -> 待研究細節。

2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」

• 查詢 ASCII 表

$ man ascii

得知：A 至 Z 的範圍在 0x41 ~ 0x5a ; a 至 z 的範圍在 0x61 ~ 0x7a 。

• 想法 : 將所有輸入字串轉為大寫 (或是小寫), 再判斷其是否在對應的區間
• 實驗 : TODO

3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對

• TODO

測驗二

開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}

個人解題思路

1. MASK = ?

1. 我首先觀察到的是 return value 的部分, 使用 mask 遮去了高位的4個位元; 因此, 我判斷此作法利用 shift 將原 input 的低位4個位元修正成我們想要的結果 (0~15的任一個值)
2. 乘上, 我觀察大小寫英文字母與數字字元在 ASCII 編碼中的低位4個 byte, 發現 : 數字字元不需要修正, 而英文字母需要 + 0x09 (e.g. 0x41 ('A') + 0x09 = 0x4a, mask 掉高位的4個 bit 後得到 0x0a = 10)
3. 考慮到數字與字母需要用到不同的 shift 修正值, 我思考要用 MASK 留下 in 中得以區別字母與數字的部分
4. 觀察大寫, 小寫字母與數字的高位4個bit, 如下 :

大寫字母字元 : 0100
小寫字母字元 : 0110
數字字元 : 0011

發現可以用 0100 來 mask 出字母與數字! 因此初步判定 MASK = 0x40

2. AAA = ?, BBB = ?

1. 基於MASK = 0x40 以及 in 只會是對應到 ASCII 中大小寫字母與數字假設, 我們得到

letter = 0x40, if in 對應到的 ASCII 為大小寫字母
letter = 0x00, else

2. 基於前述觀察 (字母需要 +0x09 的修正, 而數字不用), 可以判斷 AAA 和 BBB 其一為3, 另一個則為6

延伸問題

• 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值

想法 : 首先考慮輸入字元的個數, 如果我們想要以 word 來處理資料, 需要考慮到補 0
實驗 : TODO

測驗三

• 快速除法概念 : 將除法運算轉換成 shift operation 以及 乘法 的組合

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{   uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

其中 __uint128_t 是 GCC extension，用以表示 128 位元的無號數值。

個人解題思路

1. XXX = ?

1. 觀察 line6, 將此行對應至題目給訂的公式
   $n\ast ((2^N/d)/2^N)$, 可初步判斷這裡的 N 取的是64
2. 觀察到 D = 3 不為一個 power of 2 的數值, 因此思考題目敘述 : "我們可先估算，並將差值補償回去" 後, 判斷 line2 的 macro 應該在做此 "估算並補償的動作"
3. 有了這個初步的想法卻卡住了, 不知道為何聚集是如此定義, 因此決定直接先去 trace src/div.c
4. 程式碼的註解中解釋並證明了藉由使用 ceil(2^k / d) 作為 magic, 並且設定
   $k=32$ (能使得 n / 2^k 恆小於 1) 的情況下 :
   能使得 floor(ceil(2^k / d) * n / 2^k) 得到
   $n/d$ 在數學上正確的 quotient
5. 此時回頭檢視我們定義的 macro M, 並根據 ISO/IEC 9899:201x, UINT64_C(XXX) 將 XXX expand 至 unsigned long long int, 這個 data type 沒辦法正確地表示出
   $2^{64}$
6. 已知 C 使用 floor 處理商數的小數點, 於是我們使用 +1 來達到 ceiling
7. 我們要證明
   $floor(2^{64}/3)+1=floor((2^{64}-1)/3)+1$; 事實上, 因為
   $2^{64}\mathrm{mod}3\ne 0$, 我們定義的 macro M 在 d = 3 時永遠可以得到對的結果;

延伸問題

TODO

測驗四

延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

bool divisible(uint32_t n)
{
    return n * M <= YYY;
}

個人解題思路

1. YYY = ?

1. 先思考
   $\mathrm{\forall }n,n=3k\vee 3k+1\vee 3k+2,n<=0xffffffff$
2. 考慮
   $n\ast M$ 在這三種情況下分別可表示成以下三種形式

• if
  $n=3k,\mathrm{此}\mathrm{時}k<=0x55555555$
  • 此時
    $n\ast M=3k\ast ((2^{64}-1)/3+1)$
  • 則
    $n\ast M=k\ast (0xffffffffffffffff+3)=k\ast 2=2k$, 因為此時
    $(0xffffffffffffffff+3)$ 溢位回 +2
• if
  $n=3k+1,n\ast M=2k+M$
• if
  $n=3k+2,n\ast M=2k+2M$

可以看出在 n 這三種情況下, n*M 的值會因為數值溢位會有對應且固定的表示公式, 再來我們從答案選出一個定值, 能夠分界出 n = 3k 與 n = 3k + 1 和 n = 3k + 2 的 case

測驗五

考慮 strlower 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 in-place 的實作如下:

#include <ctype.h>
#include <stddef.h>
/* in-place implementation for converting all characters into lowercase. */
void strlower(char *s, size_t n)
{
    for (size_t j = 0; j < n; j++) {
        if (s[j] >= 'A' && s[j] <= 'Z')
            s[j] ^= 1 << 5;
        else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
            s[j] = tolower(s[j]);
    }
}

在 64 位元處理器架構 (以下針對 x86_64, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 x86_64 來說，就是 64 bits，或 8 個位元組)。沿用上述的 strlower 函式，我們用這樣的思路實作向量化的 strlower，程式碼列表如下:

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

個人解題思路

1. VV1 = ?

測驗六