2020q3 Homework2 (quiz2)

tags: sysprog2020 homework

contributed by < JKChun >

題目

測驗 1

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

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

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 & 0x8080808080808080 #(MMM) )
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

程式原理

一個 char 是1個 byte，也就是8 bit，只要跟 1000 0000 (0x80) 做 AND 運算，就可以確定是不是有效的 ASCII 字元(因為128~255第8個 bit 一定是1)，在64位元的系統中，可以一次處理8個字元，所以 mask 是 0x8080808080808080 ，而while 迴圈中的 i 一次加8個，由於字元的總數不一定是8的倍數，最後的 while 迴圈用原本的方法一個字元慢慢檢查

延伸問題

1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性
2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
   提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4

為何用到 memcpy ?

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

A~Z: 0x41~0x5A
a~z: 0x61~0x7A

#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 & 0x8080808080808080){
            return false;
        }
        uint64_t a = payload + PACKED_BYTE(128 - 'a' );  
        uint64_t z = payload + PACKED_BYTE(128 - 'z' - 1); 
        uint64_t A = payload + PACKED_BYTE(128 - 'A' );  
        uint64_t Z = payload + PACKED_BYTE(128 - 'Z' - 1); 

        uint64_t lower = (a ^ z) & PACKED_BYTE(0x80);
        uint64_t upper = (A ^ Z) & PACKED_BYTE(0x80);
        
        if ( ( lower || upper ) ){
            return true;
        }
        i += 8;
    }
    while (i < size) {
        uint64_t a = payload + (128 - 'a' );  
        uint64_t z = payload + (128 - 'z' - 1); 
        uint64_t A = payload + (128 - 'A' );  
        uint64_t Z = payload + (128 - 'Z' - 1); 

        uint64_t lower = (a ^ z) & 0x80;
        uint64_t upper = (A ^ Z) & 0x80;
        if (( lower || upper ))
            return true;
        i++;
    }
    return false;
}

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

測驗 2

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

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

程式原理

第一行是在判斷輸入是字母還是數字，由於數字0~9的 ASCII 的前4bit 都是0011，而大寫和小寫的字母的 ASCII 的前4bit分別是0100和0110，所以把輸入 in 和0x40(MASK)做 AND 運算就能辨別輸入是字母還是數字：

輸入	letter 的值
數字	0000 0000
字母	0100 0000

先看最後一行的 return，裡面有 & 0xf，這代表只取 in + shift 的後4bit，再看數字0~9的 ASCII 的後4bit 剛好就是對應的0~9，所以 shift 在輸入是字母的時候不是0，在輸入是數字的時候是某個數，接下來看大寫和小寫的字母的 ASCII 的後4bit，發現大寫和小寫的後4bit 都是一樣的，且只和對應的十進位數值差9，所以在輸入是字母時，shift的值為0x09，因此在第二行將 letter 向右位移3(AAA)和6(BBB)並做 OR 運算得到0x09

字母	ASCII	對應的十進位
a	0110 0001	10
A	0100 0001	10

延伸問題

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

TODO !!

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

程式原理

找餘數的想法：

$nmodd=n-\lfloor (\frac{n}{d})\rfloor \ast d$
目標：找出

$\lfloor (\frac{n}{d})\rfloor$，

$\frac{n}{d}$ 的商

數學式

$\frac{n}{d}=n\ast \frac{\frac{2^N}{d}}{2^N}=n\ast M\ast \frac{1}{2^N}$
為什麼程式中的

$M=\frac{2^{64}-1}{d}+1$ ?
現在還不知道 TODO!!
參考了 sammer1107 的推導以及他對 jemalloc 的講解

只要今天 n 是被 d 整除且我們選擇的 k 夠大，我們就可以用

$\lceil \frac{2^k}{d}\rceil$ 當作 magic number

$M$。要做除法時就做

$n\cdot M\cdot \frac{1}{2^k}$ 即可，對應到 c 語言中，即是乘法與位移兩個動作。

According to division rule, we can say that

$n=qd+r$ for some

$q,r\in N$ and

$r<d$. Then, we have

$\lfloor \lceil \frac{2^k}{d}\rceil \ast n\ast \frac{1}{2^k}\rfloor =q+\lfloor \frac{r}{d}+\frac{r^{\prime }}{d}\ast \frac{n}{2^k}\rfloor .$
The first and second equality comes from the same reasoning in the jemalloc case. The third equality comes from the fact that

$\frac{n}{d}=q+\frac{r}{d}$. The final equality stands because

$q$ is an integer.
The final line equals to

$q$ only if

$\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^k}<1$.

因為在

$2^k$ 不整除於 d 的時候，M 會得到

$\lfloor \frac{2^k}{d}\rfloor$ ，為了讓程式在計算 M 時都可以得到

$\lceil \frac{2^k}{d}\rceil$ 這個結果，所以讓

$M=\frac{2^{64}-1}{d}+1$ 。

延伸問題

TODO !!

測驗 4

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

程式原理

no idea
TODO !!

測驗 5

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

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

/* 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);
}

• 開頭的 #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) 是用來取 b 的後4 bit 並複製8次，如：0x23，則結果為 0x2323232323232323
• 第一個 if branch 要判斷8個字元裡有沒有不是 ASCII 的，所以 VV1 為 0x80
• 先看 *chunk ^= mask 可以得出如果字元在 A~Z 之間則 mask 一定是 0x20，不然就是 0x00，來轉小寫，所以 ((A ^ Z) & PACKED_BYTE(VV4)) 的值在 A~Z 之間要 0x80
• 又中間是做 AND 運算，所以 VV4 為 0x80
• 為了讓 A 和 Z 的第 8 bit 不一樣，所以選擇 VV2 = 0, VV3 = -1，讓在 A~Z 之間的字元經過加法後，變數 A 可以大於 128 而變數 Z 可以小於 128，不是在 A~Z 之間的字元經過加法後，變數 A 和 Z 不是都大於要不就都小於 128 。

延伸問題

將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為

TODO !!

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

程式原理

• 很重要的一點是每個 bit 是獨立的，只要管 bit 的1跟0出現幾次就好，舉例：[1, 2, 1, 2, 3, 2, 1]，換成 binary 就是[01, 10, 01, 10, 11, 10, 01]，以題目的規則看，每個 bit 不是1出現 3n 次，0出現 3n + 1 次，就是0出現 3n 次，1出現 3n + 1 次，
  $n\in 0,1,2,3,......$。
• 所以題目用 lower 紀錄出現一次的 bit，higher 紀錄出現兩次的 bit，而且只有在lower 為0 higher 才能為1，只有在 higher 為0 lower 才能為1，假如已經出現過兩次了接著又出現了，代表出現第三次，那 lower 和 higher 的 bit 皆為0
• 舉例：參考 joey3639570

以5 (101) 為例:

第一次
000 ^ 101 = 101 (lower ^=)
101 & 111 = 101 (lower &= ~higher)
000 ^ 101 = 101 (higher ^=)
101 & 010 = 000 (higher &= ~lower)
結果而論 lower 為 101 ， higher 為 000

第二次
101 ^ 101 = 000 (lower ^=)
000 & 111 = 000 (lower &= ~higher)
000 ^ 101 = 101 (higher ^=)
101 & 111 = 101 (higher &= ~lower)
結果而論 lower 為 000 ， higher 為 101

第三次
000 ^ 101 = 101 (lower ^=)
101 & 010 = 000 (lower &= ~higher)
101 ^ 101 = 000 (higher ^=)
000 & 111 = 000 (higher &= ~lower)
結果而論 lower 為 000 ， higher 為 000

• 所以 code 為：

lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;

延伸問題

1. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
2. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;

TODO !!