2020q3 Homework2 (quiz2)

contributed by < Rsysz >

tags: sysprog

測驗題

1. ASCII 編碼判斷

目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (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;
}

已知 7 位元編碼的字元隸屬於 ASCII，透過 uint64_t 也就是 long int payload 截取 str 字串陣列中前8位進行判斷，如下圖所示，與 0x80 進行 & 運算後必須等於0
而 payload 內有 8 個bytes對應8個字元，因此每個字元對應一組 0x80
MMM = 0x8080808080808080

Hexadecimal	Binary	Decimal
0x80	1000 0000	128
0x7F	0111 1111	127

memcpy 常見的實做是先檢查 memory address 是否 word aligned，如果不是會先 copy 前幾 bytes 使目前位址到 word aligned 的地方，然後以 word 而不是 byte 為單位做資料 copy。
因此同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快，有時候甚至可以用 Intel cpu 特殊的專用指令做一次 copy 整個區塊。

還要考慮 MIPS/Arm 架構中，如果硬體無法處理 misalignment，上述程式碼如果沒有 memcpy 這樣事先考慮到 alignment 的處理，會發生什麼事？
jserv

ARM 架構中部分CPU“部分支援”非對齊訪問其“單指令”操作支援非對齊，但“群指令”操作(SIMD)則不支援，如 LDM、STM、LDRD、STRD。ARMv5 指令集的CPU(一般是arm9架構)預設不支援非對齊記憶體訪問，ARMv6及以上的CPU預設支援處理大部分的非對齊記憶體地址訪問。

MIPS 架構中硬體不支援對齊訪問，但通過軟體支援，通過核心中對 alignment fault 異常處理流程中進行處理，比如將非對齊的資料訪問，通過多次訪存操作和拼接操作來處理，也可以使用類似 memcpy的方式來處理，當然代價是更嚴重的效能損失。

通常，在出現 alignment fault 時，需要分析定位原因，而不能簡單的通過核心的 fixup 或者忽略，由於 alignment fault 帶來的效能損耗是非常大的因此在很多CPU中，會將此類問題當做一種異常上報，目的就是希望工程師能修正程式碼，提升效能。

而最常見的可能導致 alignment fault 的程式碼編寫方式如:

• 指標轉換：將低位寬型別的指標轉換為高位寬型別的指標
• 使用packed屬性或者編譯選項。這樣的操作會關閉編譯器的自動填充功能，從而使結構體中各個欄位緊湊排列，如果排列時未處理好對齊，則可能導致alignment fault

參考資料

檢測英文大小寫字母

2. 16進位字串轉換

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，其他輸入都有對應的數值。

• 已知 hexchar2val('F') 和 hexchar2val('f') 回傳 15
• F 對應0x46, f 對應 0x66

Character	Hexadecimal	Binary
F	0x46	0100 0110
f	0x66	0110 0110
	0xf	0000 1111
再來看到 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

擴充版本

3. 快速除法

不懂就說不懂，不要說「不是很懂」這樣不精準的話，而且你已經不懂，還「僅供參考」什麼？會不會誤導自己和他人呢？
jserv

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

如標題所述，除法可以利用

$2^N\mathrm{進}\mathrm{行}\mathrm{加}\mathrm{速}，\mathrm{透}\mathrm{過}\mathrm{將}{\displaystyle \frac{n}{d}}=n\times {\displaystyle \frac{{\displaystyle \frac{2^N}{d}}}{2^N}}$將除法轉換為乘法和位移操作，進而減少運算成本。

已知 quotient = ((__uint128_t) M * n) >> 64 對應

${\displaystyle \frac{1}{2^N}}$ 所以

$N=64$
但對應的

$M\mathrm{卻}\mathrm{不}\mathrm{等}\mathrm{於}{\displaystyle \frac{2^N}{d}}$而是

$M={\displaystyle \frac{2^N-1}{d}}+1$
因此要證明兩者最終結果是相等的。
若以數學的角度考量

${\displaystyle \frac{M\times n}{2^{64}}}={\displaystyle \frac{({\displaystyle \frac{2^{64}-1}{d}}+1)\times n}{2^{64}}}={\displaystyle \frac{n\times 2^{64}-n}{d\times 2^{64}}}+{\displaystyle \frac{n}{2^{64}}}$

$={\displaystyle \frac{n}{d}}-{\displaystyle \frac{n}{d\times 2^{64}}}+{\displaystyle \frac{n}{2^{64}}}={\displaystyle \frac{n}{d}}+({\displaystyle \frac{d\times n-n}{d\times 2^{64}}})={\displaystyle \frac{n}{d}}+({\displaystyle \frac{(d-1)\times n}{d\times 2^{64}}})<{\displaystyle \frac{n}{d}}+{\displaystyle \frac{n}{2^{64}}}$。

由於

$n,d<2^{32}-1\mathrm{因}\mathrm{此}{\displaystyle \frac{n}{2^{64}}}<{\displaystyle \frac{1}{2^{32}}}<{\displaystyle \frac{1}{2^{32}-1}}\mathrm{且}{\displaystyle \frac{n}{d}}\mathrm{的}\mathrm{餘}\mathrm{數}\mathrm{部}\mathrm{分}\mathrm{最}\mathrm{大}\mathrm{值}\mathrm{為}{\displaystyle \frac{2^{32}-2}{2^{32}-1}}$
所以

${\displaystyle \frac{n}{d}}\mathrm{的}\mathrm{餘}\mathrm{數}\mathrm{部}\mathrm{分}\mathrm{加}\mathrm{上}{\displaystyle \frac{n}{2^{64}}}\mathrm{也}\mathrm{不}\mathrm{會}\mathrm{進}\mathrm{位}$

---

但若以程式碼的角度考量
若

$M={\displaystyle \frac{2^{64}}{d}}\mathrm{為}\mathrm{整}\mathrm{數}(\mathrm{設}\mathrm{為}K)，\mathrm{因}{\displaystyle \frac{2^{64}-1}{d}}<K\mathrm{所}\mathrm{以}M={\displaystyle \frac{2^{64}-1}{d}}+1=(K-1)+1=K$
若

$M={\displaystyle \frac{2^{64}}{d}}\mathrm{為}\mathrm{非}\mathrm{整}\mathrm{數}，\mathrm{因}{\displaystyle \frac{2^{64}-1}{d}}>K\mathrm{所}\mathrm{以}M={\displaystyle \frac{2^{64}-1}{d}}+1=K+1$
兩種情況會讓 quotient 分別等於

${\displaystyle \frac{n}{d}}\mathrm{和}{\displaystyle \frac{n}{d}}+{\displaystyle \frac{n}{2^{64}}}$但根據上述數學推論的結果，兩者得到的答案相等

因此 XXX = (f) 0xFFFFFFFFFFFFFFFF

jemalloc 的除法原理

$n$為被除數,

$q$為商,

$d$為除數
假設

$n=q\times d，\mathrm{已}\mathrm{知}n,d\mathrm{求}q=n/d$

$=\lfloor \lceil {\displaystyle \frac{2^k}{d}}\rceil \times {\displaystyle \frac{n}{2^k}}\rfloor =\lfloor {\displaystyle \frac{2^k+r}{d}}\times {\displaystyle \frac{n}{2^k}}\rfloor ，k\mathrm{為}\mathrm{任}\mathrm{意}\mathrm{整}\mathrm{數}，\mathrm{而}r=(-2{)}^{k}modd$

$\mathrm{將}\lfloor {\displaystyle \frac{2^k+r}{d}}\times {\displaystyle \frac{n}{2^k}}\rfloor \mathrm{展}\mathrm{開}\mathrm{為}\lfloor {\displaystyle \frac{2^k}{d}}\times {\displaystyle \frac{n}{2^k}}+{\displaystyle \frac{r}{d}}\times {\displaystyle \frac{n}{2^k}}\rfloor =\lfloor {\displaystyle \frac{n}{d}}+{\displaystyle \frac{r}{d}}\times {\displaystyle \frac{n}{2^k}}\rfloor$

$\mathrm{因}\mathrm{假}\mathrm{設}n/d\mathrm{為}\mathrm{整}\mathrm{除}，\mathrm{所}\mathrm{以}n/d\mathrm{的}\mathrm{小}\mathrm{數}\mathrm{部}\mathrm{分}\mathrm{為}0，\mathrm{因}\mathrm{此}\mathrm{式}\mathrm{子}\mathrm{可}\mathrm{以}\mathrm{化}\mathrm{簡}\mathrm{為}{\displaystyle \frac{n}{d}}+\lfloor {\displaystyle \frac{r}{d}}\times {\displaystyle \frac{n}{2^k}}\rfloor$

也就是當

${\displaystyle \frac{r}{d}}\times {\displaystyle \frac{n}{2^k}}<1$，

$n/d=\lfloor \lceil {\displaystyle \frac{2^k}{d}}\rceil \times {\displaystyle \frac{n}{2^k}}\rfloor$就會成立

因

$r\mathrm{是}{\displaystyle \frac{2^k}{d}}\mathrm{的}\mathrm{餘}\mathrm{數}\mathrm{因}\mathrm{此}r<d\mathrm{且}r/d<1$總是成立，所以只需滿足

${\displaystyle \frac{n}{2^k}}<1$
又

$n\mathrm{為}32bits\mathrm{的}\mathrm{數}，\mathrm{最}\mathrm{大}\mathrm{值}\mathrm{為}{2}^{32}-1，\mathrm{因}\mathrm{此}\mathrm{可}\mathrm{以}\mathrm{令}k=32\mathrm{來}\mathrm{確}\mathrm{保}{\displaystyle \frac{n}{2^k}}<1$

4. 倍數判斷

已知 D = 3 M = (0xFFFFFFFFFFFFFFFF / D) + 1 = 0x5555555555555556

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

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

• 3kM = 2k
• (3k+1)M = 3kM + M = 2k+M
• (3k+2)M = 3kM + 2M = 2k + 2M
  因此只有 (c) M - 1, (d) M >> 1 符合要求
  但答案的 YYY = (c) M - 1

注意共筆書寫要求：中英文之間用一個半形空白字元區隔，從小處做起！
jserv

5. 字串大小寫轉換

#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
e.g. 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
	128	1000 0000
因此可得知當
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

延伸問題 將前述測試程式 main 函式的 char str[] 更換為 char *str，會導致
Segmentation fault (core dumped)的發生。
根據C語言規格書ISO/IEC 9899:1999p.130

The contents of the arrays are modifiable. On the other hand, the declaration
char *p = "abc";
defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal.
If an attempt is made to use p to modify the contents of the array, the behavior is undefined.

嘗試使用 p 去修改 arrary 內的值是屬於 undefined behavior

6.4.5 String literals

The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.

又提到會將內容初始化為指定大小的靜態陣列，因此使用 char *str 相當於 const char *str

6. 單次數尋找

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

是有限狀態機的味道，而本題題解屬於Mealy機，輸出依賴於輸入和狀態
首先構建一個真值表如下圖所示

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

當出現第三次時代表此數並非我們所尋找的數，因此直接重置狀態為 00

$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，得到題解程式碼如上圖。

延伸問題 2

延伸問題 3