2020q3 Homework2 (quiz2)

contributed by < chi-ming5566 >

測驗題

---

作業要求

• 重新回答第 2 周測驗題，連同附帶的「延伸問題」。
• 比照 課前測驗參考解答: Q1的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。

---

測驗一

#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;
}

此函式是用來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元。

但逐一字元比對的效率低，在 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.解釋上述程式的運作原理，特別是為何用到 memcpy 呢？
2.將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對。
提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對。

• payload 會去抓 str 字串陣列中前 8 位與 0x80 進行 & 運算後需等於 0，而 payload 內有 8 個 bytes 對應8個字元，因此每個字元對應一組0x80，故 MMM = 0x8080808080808080。

memcpy(&payload, str + i, 8);

• 是由 str + i 指向地址為起始地址的連續 8 個位元組的資料，再複製到以 payload 指向地址為起始地址的空間內。

---

測驗二

開發解析器 (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;
}

已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15，且 hexchar2val('0') 回傳 0，其他輸入都有對應的數值。

以下摘自 ASCII 表格

• '0', '1', '2', …, '9' 對應到 0x30, 0x31, 0x32, … 0x39
• 'a', 'b', 'c', …, 'f' (小寫) 對應到 0x61, 0x62, 0x63, …, 0x66
• 'A', 'B', 'C', …, 'F' 對應到 0x41, 0x42, 0x43, …, 0x46

延伸問題:
1.解釋上述程式的運作原理;
2.將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值

• 已知 hexchar2val('F') 和 hexchar2val('f') 回傳 15。
• F 對應0x46, f 對應 0x66 。
• 所以 0x46 轉換成二進位就是 0100 0110，而 0x66 則是 0110 0110。

因為return (in + shift) & 0xf ，所以 F 與 f 輸入的 in + shift 最低位的 4 個 bits 必為 1111，轉換成十進位就是 15 。

Character	Binary
F	0100 0110
f	0110 0110
0x40	0100 0000

由此可知兩者在最高位 4 個 bits 只有 1 個 bit 相同，於是MASK = ? 0x40 。

Character	Binary
0x40	0100 0000
letter	0100 0000
F	0100 0110
f	0110 0110
in+shift	XXXX 1111
根據 MASK = 0x40 的結果我們可以知道 letter 在兩種輸入情況下皆等於 0100 0000，又in + shift 最低位的 4 個 bits 等於 1111，於是讓 letter 分別做兩次右移補滿 F 和 f 的最低位 0110 ， 於是
AAA = 3
BBB = 6

---

測驗三

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 位元的無號數值。
預期 quickmod(5) 會得到 2, quickmod(55) 得到 1, quickmod(555) 得到 0 (555 是 3 的倍數)。

請補完程式碼。

XXX = (f) 0xFFFFFFFFFFFFFFFF

---

測驗四

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

以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即白痴是三的倍數)

請補完程式碼。

令 n=3a, 3a+1, 3a+2 (a為非負整數)
若 a=1 ， 因為 3M > 0xFFFFFFFFFFFFFFFF (overflow) 所以 3M = 0x0000000000000002
求三者最小值:

• 3aM = 2a
• (3a+1)M = 3aM + M = 2a+M
• (3a+2)M = 3aM + 2M = 2a + 2M
  (c) M - 1 符合要求，所以YYY = (c) M - 1 。

---

測驗五

#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);
}

PACKED_BYTE 的作用是將輸入 LSB 的 8 bits 擷取後重複擴充至 64 個 bits，例如: PACKED_BYTE(0xAB) 會得到 0xABABABABABABABAB，如同第一題以0x80對 ASCII 範圍內的字元進行檢測，因此 VV1 = (e) 0x80

再來看到uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2 ，而

• ('a' ^ ' ') // 得到 'A'
• ('A' ^ ' ') // 得到 'a'

此外0x80 >> 2 = ' '可以知道 A ^ Z 的數值可以決定這 8 個字元哪一個要做大小寫轉換
因此只有字元為大寫時，A ^ Z的 MSB 才能為 1
(128 - 'A' + char + VV2) ^ (128 - 'Z' + char + VV3)

char	Decimal	Binary
A	65	0100 0001
Z	90	0101 1010

由此可得知當
char >= 'A' 時 uint64_t A 的 MSB 為 1
char >= 'Z' 時 uint64_t Z 的 MSB 為 1
但當 char = Z 時為了使 A ^ Z 的 MSB 為 1 還需額外減 1
所以
VV2 = (b) 0
VV3 = (a) (-1)
VV4 = (e) 0x80

---

測驗六

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= KKK;
        higher ^= nums[i];
        higher &= JJJ;
    }
    return lower;
} 

首先建一個真值表:

higher	lower	input	higher_output	lower_output
0	0	0	0	0
0	1	0	0	1
1	0	0	1	0
0	0	1	0	1
0	1	1	1	0
1	0	1	0	0

$lower\mathrm{\_}output=\overline{input}\times \overline{higher}\times lower+input\times \overline{higher}\times \overline{lower}=\overline{higer}\times input\oplus lower$

$higher\mathrm{\_}output=\overline{input}\times higher\times \overline{lower}+input\times \overline{higher}\times lower$

但題解中 higer 計算並未使用到前次 lower 的狀態，因此修改真值表，
而這次就嘗試使用 lower_output 計算 higher_output。

higher	lower(lower_output)	input	higher_output
0	0	0	0
0	1	0	0
1	0	0	1
0	1	1	0
0	0	1	1
1	0	1	0

$higher\mathrm{\_}output=\overline{input}\times higher\times \overline{lower}+input\times \overline{higher}\times \overline{lower}=\overline{lower}\times input\oplus higher$

因此改用lower計算higher，得到
KKK = ~higher
JJJ = ~lower