2020q3 Homework2 (quiz2)

contributed by < chewei3 >

測驗 1

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

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

答案

• MMM = 0x8080808080808080
• 7位碼 ASCII 是以 7 位元二進位數字編碼，可表示 128 個字元，由第一段程式碼可以知道，str[i] & 0x80 可以檢查一個 char 的 MSB 是不是 1 ，來判斷是這個是否為有效的 ASCII 字元
• 為了一次比對一個 word ，在 64 位元的架構下，只要擴展前面比對 1-byte 的 mask ，用 0x8080808080808080 就可以一次比對 8-byte

延伸問題

1. 為何用到 memcpy?

2. 給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母

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

測驗 2

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

以下摘自 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

答案

• mask = 0x40
• AAA = 3
• BBB = 6
• 0 的二進位表示法為 0011 0000， A 的二進位表示法為 0100 0001，a 的二進位表示法為 0110 0001，顯然 letter 與否由第 6 bit 決定，number 的後 4 bits 是轉換後的 value ， A 及 a 如果要轉成 **** 1010 ，可以用第 6 bit (也就是letter)達成，因此 AAA = 3，BBB = 6

測驗 3

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

答案

XXX = 0xFFFFFFFFFFFFFFFF

因為

$nmodd=n-\frac{n}{d}\times d$ ，由此可看出

$quotient=\frac{n}{d}$ ，又因為題目提示

$quotient=\frac{n}{d}=n\times \frac{\frac{2^n}{d}}{2^n}$ ，可以得出

$2^n=64$ ，因此

$M=\frac{2^{64}}{d}$，而

$\frac{2^{64}}{d}$ 跟

$\frac{XXX}{d}+1$ 長的不太一樣，顯然

$\frac{XXX}{d}+1$是為了替代 2⁶⁴ 所得到的運算式。

因為延伸問題有提到 src/div.c(https://github.com/jemalloc/jemalloc) 有運用類似的技巧，註解中有提供

$n/d$ 證明如下

$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 ,r=d-2^{k}modd$

$=\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$

$={\displaystyle \frac{n}{d}}+\lfloor {\displaystyle \frac{r}{d}}\times {\displaystyle \frac{n}{2^k}}\rfloor$

如果

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

$n/d=$

$\lfloor \lceil {\displaystyle \frac{2^k}{d}}\rceil \times {\displaystyle \frac{n}{2^k}}\rfloor$，因此 k = 32

同理上面的 k = 64，最接近的答案為 0xFFFFFFFFFFFFFFFF

延伸問題

由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;

TODO:

測驗 4

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

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

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

• ( c ) M - 1

已知 D = 3，M = (0xFFFFFFFFFFFFFFFF / 3) + 1 = 0x5555555555555556
令 n = 3k, 3k+1, 3k+2， n * M = 3kM, (3k+1)M, (3k+2)M
又 3M = 0x0000000000000002，因此

• 3kM = 2k
• (3k+1)M = 3kM+M = 2k+M
• (3k+2)M = 3kM=2M = 2k+2M

(a) 矛盾，當 n = 3k+1 時不可被3整除，但 M <= M+1成立
(b) 矛盾，當 n = 3k+1 時不可被3整除，但 M <= M成立
(d) 矛盾，

$(M>>1)\simeq M/2$ ，n * M <= M/2，n <= 1/2，但 n 為 uint32
(e) 矛盾，當 n = 3k+1 時不可被3整除，但 M <= 2M 成立

測驗 5

考慮 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]);
    }
}

針對 extended ASCII，我們呼叫 C 語言標準函式庫的 tolower，需要留意到在不同的語系 (locale)，字母順序和大小寫的定義可能異於我們認知的英文字母。以下摘自手冊:

If c is a lowercase letter, toupper() returns its uppercase equivalent, if an uppercase representation exists in the current locale. Otherwise, it returns c.

語系對程式碼的影響不能輕忽，舉例來說，若語系設定為捷克語，以 “Ch” (屬於 digraph，二合拉丁字母，常見於西歐語言) 開頭的字串要排在 “H” 之後，但單看字母的話，“C” 要在 “B” 之後。不過，如果明確只處理英美語系 (American/British English)，上述程式碼列表的第 9 及第 10 行可略去。

捷克字母 (依序)
A a Á á B b C c Č č D d Ď ď E e É é Ě ě F f G g H h Ch ch I i
Í í J j K k L l M m N n Ň ň O o Ó ó P p Q q R r Ř ř S s Š š
T t Ť ť U u Ú ú Ů ů V v W w X x Y y Ý ý Z z Ž ž

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

對應的測試程式碼如下:

#include <stdio.h>
#include <string.h>
int main()
{
    /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
    char str[] =
        "This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever.  You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
    int n = strlen(str);
    strlower_vector(str, n);
    puts(str);
}

參考執行輸出:

this ebook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. you may copy it, give it away or re-use it under the terms of the project gutenberg license included with this ebook or online at www.gutenberg.net

• PACKED_BYTE(0x80)是取 LSB 的後 8 bits 擴展到前面位置，因此出來的結果為0x8080808080808080 ，且判斷 ASCII code 的方法如測驗一，因此 VV1 = 0x80
• 若要將 A~Z 轉換成 a~z ，可以使用 xor ，('A' ^ ' ') = a，因此可以知道 mask = 0x2020202020202020，因此 VV4 = 0x20<<2 = 0x80，可以知道 (A ^ Z) & PACKED_BYTE(0x80) 是做大小寫轉換，且轉換的條件是(A ^ Z)的 MSB 為 1
• 若 VV2=0 VV3=0，若字元為 'A' 則 A 的 MSB 為 1， Z 的 MSB 為 0，但是字元為 'Z' 的時候雖然 A 的 MSB 為 1， Z 的 MSB 也是 1， 所以 VV3 = -1

測驗 6

LeetCode 137. Single Number II:

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: [2,2,3,2]
Output: 3

Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99

考慮以下程式碼為 LeetCode 137. Single Number II 的題解:

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