2020 sysprog Homework2 (quiz2)

tags: sysprog

contributed by < sciyen >

• 2020 sysprog Homework2 (quiz2)
  • Q1 is_ascii()
  • Q2 hexchar2val()
  • Q3 quickmod(uint32_t n)
  • Q4 divisible(uint32_t n)
  • Q5 strlower
    • 解析 void strlower(char *s, size_t n) 程式碼原理
    • 利用 64 bit 架構做運算
  • Q6 LeetCode 137. Single Number II:
    • 首先看 XOR 的特性：

Q1 is_ascii()

題目：

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

已知 extended ASCII 的第8個 bit 為1，若以單一個 byte 來看，用以下方式可以判斷第8個 bit 是否為1

int b = byte & 0x80;

For example:
0b11000111
0b10000000 -> 0xf0
0b10000000

利用相同方式，若有 8 byte，則 Mask 以一個 byte 為單位，用 8組。

0x8080808080808080

Memory alignment problem

由於傳入的參數 str 可能是記憶體中的任意位置(不一定會 alignment )，因此若直接對該記憶體操作有可能因為 unalignment 必須讀兩個記憶體區段再合併導致效能變差，因此利用 memcpy() 強制將記憶體 alignment 後再進行後續操作。

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

Q2 hexchar2val()

題目：將十六進位表示的字串 (hexadecimal string) 轉為數值

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40;
    const uint8_t shift = (letter >> 3) | (letter >> 6);
    return (in + shift) & 0xf;
}

注意 ASCII 中數字與英文字的表示方式

• 數字 0x30~0x39, 前4個 byte 皆為 0b0011
• 小寫英文 0x61~0x66, 前4個 byte 為0b0110
• 大寫英文 0x41~0x46, 前4個 byte 為0b0100

1. 為了判斷是否為英文，利用第一個 MASK 判斷前 4 byte 中的 4 位置是否為1， 因此 MASK 為0x40。因此 letter 的意義為 in 是 >=10 的值。
2. 接下來，若 in 是 >=10 的值，則必須要創造出一個 10 加進去答案裡面，又若 in>=10 ， letter = 0b01000000，因此將 letter 右移3格得到 0b00001000，右移6格得到 0b00000010，做 or 運算後得到 0b00001001 也就是9。

	0b01000000
3	0b00001000
6	0b00000001
OR	0b00001001

4. 最後將 in 與 shift 相加，若 in 為數字，則 shift 為0；若 in 為 A~Z 或 a~z ，則 shift 為9，由於 A~Z 及 a~z 的後4個 byte 皆對應到 A=1, B=2,…，因此 A 為9+1=10，以此類推…
5. 最後，與0x0f做 AND 運算將剩餘的前 4 byte 濾掉。

Q3 quickmod(uint32_t n)

題目：該算法將除法變形為 乘法 與 shift 的組合。

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (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;
}

問題解析

由原式中

$$\frac{n}{d}=n\times \frac{\frac{2^N}{d}}{2^N}$$
可以發現 M 應為式中

$\frac{2^N}{d}$ 的部分，而 N 為64，但由於

$2^{64}$ 恰好進一位，導致記憶體位置不夠，因此用 0xFFFFFFFFFFFFFFFF 代替，最後再加1。

程式碼說明

1. 對於 #define 代表利用預處理器先行計算 ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1)) 並視為 constant 處理，因此可以大幅減少執行時期的計算。
2. 對於式中的
   $\frac{1}{2^{64}}$ ，由於其為2的倍數，可以用 shift 快速處理。

Proof

$\frac{2^N}{d}$ 於程式中寫為

$\frac{2^N-1}{d}+1$
假設：商數為 q ，餘數為 r 且

$q,r\in \mathbb{N}$
依據情況可以分為下列兩種：

• $2^N$ 整除 d：
  
  $$\{\begin{array}{l}{2}^N=q\times d\\ 2^N-1=(q-1)d+(d-1),ifd>1thend-1>0\end{array}$$
  因此 q 必定比原式少1
• $2^N$ 不整除 d：
  
  $$\begin{gathered} \{\begin{array}{l}{2}^N=q\times d+r,where1<r<d\\ 2^N-1=(q-1)d+(r-1)\end{array} \\ \because 1<r<d \\ \therefore 0<r-1<d-1 \end{gathered}$$
  d-1必定無法進位，因此 q 必定比原式少1

結論：
不管

$\frac{2^N-1}{d}$中的 N 及 d 為多少，所得的 q 必定較

$\frac{2^N}{d}$ 少1，因此

$\frac{2^N}{d}$ 於程式中寫為

$\frac{2^N-1}{d}+1$。

延伸問題

Q4 divisible(uint32_t n)

Q5 strlower

解析 void strlower(char *s, size_t n) 程式碼原理

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

觀察 ASCII code 可以發現，其大寫字母與小寫字母差在第 5 個 bit ，例如：
A: 0x41 0100 0001
B: 0x61 0110 0001

因此若要將大小寫互換，只要將第 5 個 bit 作 not 運算即可。

利用 64 bit 架構做運算

一次對 8 個 byte 做處理以加速計算：

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

• 12行：由於 char array 為連續的記憶體，透過 uint64_t 指標的方式取值可以獲得連續 8 byte 的記憶體。
• 5行：由於要做 64 bit 乘法運算，因此將 b 強制轉為 uint64_t ，同時，為確保只有第一個 byte

Q6 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 &= ~higher;
        higher ^= nums[i];
        higher &= ~lower;
    }
    return lower;
} 

首先看 XOR 的特性：

XOR 重複做兩次後會變回原本的數字

5: 00000101
5: 00000101
------------
A: 11111111
5: 00000101
------------
A: 00000101

如果從 0 開始，對 0 做 2 次一樣的 XOR 後會變回 0 。
Note：可以觀察到，對任意數做兩次一樣的 XOR 後都會變回原本的數，其原因也很明確，因為相同的數做 XOR 後必定全為 1 ，然後任意數對 1 做 XOR 後，其值不變。

0: 00000000
5: 00000101
------------
A: 11111010
5: 00000101
------------
A: 00000000

5: 00000101
3: 00000011
------------
A: 11111001
5: 00000101
------------
A: 00000011
5: 00000101
------------
A: 11111001
5: 00000101
------------
A: 00000001