2020q3 Homework2 (quiz2)

contributed by < unknowntpo >

測驗 1

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

Answer: MMM = (d) 0x8080808080808080

自我問答

payload 的作用是？
把要比對的數值 (大小為 8 bytes) copy 到 payload 上，在對 payload 做位元操作
可以直接對 str[] 做 check 而不用額外 copy 到 payload 上嗎？
- 沒辦法，以 str[1] 這個 object 為例，它的大小是 1 個 byte，而如果要做一次 8 個 byte 的比對的話就需要另一個大小為 8 bytes 的 object，這也是 payload 的作用

第一個 while 判斷式為 while ((i + 8) <= size),
- 假設 size == 8, 在 str[] 後的第一個 byte 藏有 non-ascii code 的話，這樣會不會出現明明 str[] 內都是 ascii, 但是判斷結果卻是 non-ascii 呢？
- 我的解答:
  - 事實上 str[size] 永遠都會是 null character , 所以並不會發生 copy 到不屬於 str[] 的東西
第一次與第二次的 while loop 對於 i 的邊界不一樣，或許能改成
- while((i + 8) < size)
- while (i < size)?
- 答案是不行
  - 第一個 while 是確認是否有足夠的 8-byte chunck 來複製到 payload
  - 第二個 while 是確認一次檢查一個 byte 的時候不會超出邊界
    - 在第二個 while 如果使用 i <= size 的話，就會檢查到 null character 了！
      - 這不符合我們的預期

TODO: 做實驗來驗證自己的假設


assume str[] = "a"
size == 8
                    i + 8
    i               size 
idx 0 1 2 3 4 5 6 7 8
str 0 1 1 0 0 0 0 1 x
    | ____________|
           'a'

完整 test code

































































/*
 * isascii: Check if all the elements at an array is ascii character or not
 * Ref:
 *      2020q3 Homework2 (quiz2) Question 1: https://hackmd.io/@sysprog/2020-quiz2
 *      My note: https://hackmd.io/@unknowntpo/quiz2
 */

/* Change to 1 if we want to test non ascii character */
#define TEST_NON_ASCII 1

/*

(a) 0x0080008000800080
(b) 0x8000800080008000
(c) 0x0808080808080808
(d) 0x8080808080808080  <-- right answer
(e) 0x8888888888888888
(f) 0xFFFFFFFFFFFFFFFF

*/
/* Define MMM */
#define MMM 0x8080808080808080

#include <stdio.h>
#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;

    /* Check the character 8 bytes (1 word in 64-bit cpu) at a time */
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM) // MMM
            return false;
        i += 8;
    }
    /*
     * Not enough words,
     * so check the character 1 byte at a time
     */
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

int main()
{
    char c[] = "12345678";
    /* Insert non ascii character */
#if TEST_NON_ASCII
    c[1] = 128;
#endif
    printf("is %s ascii ? %s\n", c, is_ascii(c, strlen(c)) ? "true" : "false");

    return 0;
}

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

AAA = ?

首先觀察字元的規律(用黃色螢光筆標示)

char	ascii code	b6	b5	b4	b3	b2	b1	b0	number to transfer:
`'0'`	0x30	0	1	1	0	0	0	0	0000
`'1'`	0x31	0	0	0	0	0	0	1	0001
`'2'`	0x32	0	0	0	0	0	1	0	0010
`'9'`	0x39	0	1	1	1	0	0	1	1001
`'A'`	0x41	1	0	0	0	0	0	1	1010
`'a'`	0x61	1	1	0	0	0	0	1	1010
`'F'`	0x46	1	0	0	0	1	1	0	1111
`'f'`	0x66	1	1	0	0	1	1	0	1111

可以發現:

要轉換的值其實就是那個 character 的 lower 4 bits
e.g. '0' = 0x30 = [001100000]₂ 我們要擷取的就是後 4 bits 0000

設計 ascii table 的人真的太有智慧了，處處是玄機呢！

由解答回推運算流程
MASK = (c) 0x40 [0100 0000]₂
AAA = (a) 3 [0000 0011]₂
BBB = BBB = (a) 6 [0000 0110]₂






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

assume in 為 'f'[0110 0110]₂

line 3:
- 經由上面的表格，我們可以觀察到，只有當某個數字是英文字母而不是數字時，b6 才是 1
- 所以可以透過這個特性檢查我們的 in 是否為英文字母
  - 如果 in 是英文字母，letter == 0x40
  - 如果 in 是數字，letter == 0x0
```
letter := 'f'         &  0x40
        = [0100 0001] & [0100 0000]
        = [0100 0000]
```
line 4,5:

shift := (letter >> 3) | (letter >> 6)
       = [0000 1000]   | [0000 0001]
       = [0000 1001]

發現 shift 的作用是如果 in 是 letter 的話，就讓 in + 9
- 因為 a 在 16 進位理面代表 10,

char	ascii code	b2	b1	b0	lower 4 bits 代表的數值
'a'	0x41	0	0	1	1
'b'	0x42	0	1	0	2
'c'	0x43	0	1	1	3
'd'	0x44	1	0	0	4
'e'	0x45	1	0	1	5
'f'	0x46	1	1	0	6

可以發現只要把每個 letter 的數值 + 9，再 Mask 掉不必要的 higher 4 bits, 就會等於最終我們要轉換的數字了！

+9 這個動作就對應到 (letter >> 3) | (letter >> 6)
- 因為如果 in 是英文字母的話， letter == 0x40
  - 0x40 >> 3 == 0x08
  - 0x40 >> 6 == 0x01
  - 兩者做完 | 運算剛好是 9 !
line 5:

return value := (in + shift) & 0xf
              = ([0110 0110] + [0000 1001]) & [0000 1111]
              = [0110 1111] & [0000 1111]
              = [0000 1111]
              = 15

其實 shift 這個變數改成 offset 更為恰當！
- 因為他就是把字母從 lower bits == 1 (a), 2 (b) 3, ©，給他們一個 offset, 讓他們對應到 10 (a), 11 (b), 12 © ,13 (d) …

TODO: 修飾說明語句

Chang Chen ChienFri, Sep 25, 2020 8:10 AM

延伸問題:

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

Hexspeak

測驗 3

除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如

\frac{n}{d}

在分子和分母分別乘上

2^{N}

後，得到等價的

n \times \frac{\frac{2^{N}}{d}}{2^{N}}

，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當

d

(除數) 的數值是已知的狀況下，

\frac{2^{N}}{d}

可預先計算，也就是說，

\frac{n}{d}

可轉換為乘法和位移操作，進而減少運算成本。不過，顯然

\frac{2^{N}}{d}

無法總是用整數來表達 (僅在

d

是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。

重新檢視

\frac{n}{d} = n \times \frac{\frac{2^{N}}{d}}{2^{N}}

，當我們想將

n

除以

4

時，就相當於乘以

0.25

，所以我們可將

\frac{5}{4}

改為

5 \times 0.25

，我們得到整數的部分 (即

1

)，和小數部分 (即

0.25

)，後者乘以

4

就是

1

，也就是餘數。下方程式碼展示這概念:

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 位元的無號數值。

GCC: C Extensions: 128-bit Integers

預期 quickmod(5) 會得到 2, quickmod(55) 得到 1, quickmod(555) 得到 0 (555 是 3 的倍數)。

請補完程式碼。

作答區

XXX = ?

(a) 0x00F000F000F00080
(b) 0xF000F000F000F000
(c) 0x0F0F0F0F0F0F0F0F
(d) 0xF0F0F0F0F0F0F0F0
(e) 0x8888888888888888

完全看不懂 …
先從整數除法開始下手！
LeetCode 29: Divide Two Integers 解析

數學推導

摘自 < WeiCheng14159> 同學的數學推導

$\begin{aligned} n % 3 & = n - ⌊ \frac{n}{3} ⌋ \times 3 \\ = n - ⌊ n \times \frac{\frac{2^{64}}{3}}{2^{64}} ⌋ \times 3 \\ = n - ⌊ (n \times \frac{2^{64}}{3}) \times \frac{1}{2^{64}} ⌋ \times 3 \\ = n - ((n \times M) >> 64) \times 3 \end{aligned}$

Macro M 的解析

#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))

第二行同乘
$2^{64}$ 答案是否與之前一樣呢？
$\frac{2^{64}}{D}$ 何時為整數？
如何用 integer 計算
$\frac{n}{d}$
- 如何確保精確度，不論
  $\frac{2^{64}}{D}$ 是否為整數
UINT64_C 是什麼？
- integer lieral
  - ref: gnu.org
  - UINT64_C 功用是在輸入的東西後面利用 ## 接上 ULL
  - ULL 作用是？
    - specify 這個 literal 的 data type unsigned long long
    - 確保運算結果不會 overflow
      - stackoverflow 解答
      - 示範

TODO: run fastdiv to profile the behavior of macro M
回答如何確保精確度，不論

\frac{2^{64}}{D}

是否為整數

不懂: 整數除法上下乘以

2^{64}

後結果是否一樣

jemalloc 的 `div.c`

假設我們有

n = q \times d

,
其中

n

q

d

都是正整數，

n

和

d

已知
我們的目標是不使用除法運算來求出 q = n / d
對於任何 k,
我們可以得到 q =

⌊ ⌈ \frac{2^{k}}{d} ⌉ \times \frac{n}{2^{k}} ⌋

我們要找出他在何種條件下等於

\frac{n}{d}

上式又可寫成

⌊ \frac{2^{k} + r}{d} \times \frac{n}{2^{k}} ⌋

其中

How do we get r?

$⌈ \frac{2^{k}}{d} ⌉$ 如何變成
$\frac{2^{k} + r}{d}$ ?

$r = (- 2^{k}) \mod d$

代入 r, 展開式子可得

= ⌊ \frac{2^{k}}{d} \times \frac{n}{2^{k}} + \frac{r}{d} \times \frac{n}{2^{k}} ⌋

= ⌊ \frac{n}{d} + \frac{r}{d} \times \frac{n}{2^{k}} ⌋

因為前提是

\frac{n}{d}

為整數，所以上式也可以寫成

\frac{n}{d} + ⌊ \frac{r}{d} \times \frac{n}{2^{k}} ⌋

如果可以滿足

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

則

\frac{n}{d}

(除法運算) 就可以簡化成

⌊ ⌈ \frac{2^{k}}{d} ⌉ \times \frac{n}{2^{k}} ⌋

(乘法與 bitwise shift)

因為 r < d 且 r / d < 1 總是滿足，為使

\frac{n}{2^{k}}

，對於不會超出

2^{32}

的 n，可以令 k = 32 來滿足此條件

TODO: 解釋 magic number

測驗 4

測驗 5

測驗 6

Reference

2020q3 第 2 週測驗題
 作業區
 RinHizakura 同學共筆