2020q3 Homework2 (quiz2)

contributed by < shauming1020 >

tags: `homework`

測驗1



















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

1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？

一個 ASCII 字元開頭的 bit 為 0，可利用 mask 0x80 (0b10000000) 直接與一個字元做比較，原第一段程式碼 if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */ 逐一比較 1 個字元（8-bits）
上述程式碼改採用一次比較 8 個字元（64-bits） 來判斷，因此可以很直觀的得到 mask MMM 為 0x8080808080808080*
優化的 memcpy 算法會 data alignment，加速 cpu 運算　
https://www.embedded.com/optimizing-memcpy-improves-speed/

i = 0, str + i:

Address	1 byte	Char
0x56440dc9e9a0	0100 0001	A
0x56440dc9e9a1	0100 0010	B
…	…	…
0x56440dc9e9a7	0100 1000	H

i = 8, str + i:

Address	1 byte	Char
0x56440dc9e9a8	0100 0001	A
0x56440dc9e9a9	0100 0010	B
…	…	…
0x56440dc9e9af	0100 1000	H

payload

0100 1000 0100 0111 … 0100 0010 0100 0001
Mask (MMM)
1000 0000 1000 0000 … 1000 1000 1000 1000
–-

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

逐一字節的判斷












bool is_alpha(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++) {
        int diff_A = str[i] - 'A', diff_a = str[i] - 'a';
        if ((0 <= diff_A && diff_A < 26)  ||
           (0 <= diff_a && diff_a < 26))
            return true;
    }
    return false;
}

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

測驗2

1.解釋上述程式的運作原理






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

#3 const uint8_t letter = in & MASK;

觀察字母 'A', 'a' 的 ASCII，可以發現兩者皆大於 0x0100_0000 (0x40)，因此可以用 Mask 0x40 來偵測該 in 是否為字母，如果是字母的話則 letter 就會被設成 0x40

#4 const uint8_t shift = (letter >> AAA) | (letter >> BBB);

觀察字母 'A', …, 'F' 及 'a', …, 'f' 的後 4 個 bits，為 '0001', …, '0110'
而要將 'A', 'a' 輸出成 10 (0b1010) 且 'F', 'f' 輸出成 15 (0b1111)
根據最後一行提示 #4 return (in + shift) & 0xf;
- &0xf 保留後 4 個 bits
- in + shift 要恰為 (0b1010), …, (0b1111)
因此 shift 得為 0b00001001
- 可利用 letter >> 3 | letter >> 6 得到
MASK = 0x40，AAA = 3，BBB = 6

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






























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

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40;
    const uint8_t shift = (letter >> 3) | (letter >> 6);
    return (in + shift) & 0xf;
}
uint64_t hexspeak(char str[])
{
    int len = strlen(str);
    if (len > 18)
        return NULL;
    if (str[0] != '0' || (str[1] != 'x' && str[1] != 'X'))
        return NULL;

    uint64_t res = 0, x = 0;
    for (int i = len-1, n = 0; i >= 2; i--, n+=4) {
        x = hexchar2val(str[i]) << n;
        res += x;
    }
    return res;
}
main () {
    uint64_t x = hexspeak("0x0B00B135"); // 184594741
    printf("%i" , x);
}

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

1.解釋上述程式的原理

乘法和位移操作

\frac{n}{d}

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

#6 uint64_t quotient = ((__uint128_t) M * n) >> 64;

右移 64 bits 相當於除
$2^{64}$
用 __uint128_t 來 catch
$M * n$ 的高位 bit，擴大乘法後可表示的數值範圍
將程式碼整理成數學式
$\frac{(M * n)}{2^{64}}$
#2 #define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))，其中
$M = \frac{2^{64}}{d}$
$=$
$⌊ \frac{X X X}{d} ⌋ + 1$
$\frac{2^{64}}{d}$ 無法總是用整數來表達，利用可表示數值範圍的最大值來估算除 d 的結果，再將差值補回去
64-bits 的最大值 XXX = 0xFFFFFFFFFFFFFFFF 與
$2^{64}$ 恰為 1，而除 d 後最壞情形是如
$⌊ 1.999 . . ⌋ = 1$ ，捨去了小數點後非常接近 1 的值，因此一概將取完 floor 的值補上修正值 1

2. jemalloc

測驗4

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




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

$⌊ \frac{n}{d} ⌋ = (n * M) >> 64$
M 為估算
$\frac{2^{64}}{d}$ 的結果，
$n * M$ 為
$\frac{n}{d}$ 乘上
$2^{64}$ ，即
$\frac{n}{d}$ 小數的部份
$M - 1 =$
$⌊ \frac{0 x F F . . F F}{d} ⌋$ 為
$\frac{1}{d}$ 乘上
$2^{64} - 1$ ，即
$\frac{1}{d}$ 小數的部份
如果 n 要可被 d 整除，表
$\frac{n}{d}$ 小數的部份 <
$\frac{1}{d}$ 小數的部份
YYY = M - 1

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

1.解釋上述程式的原理

從 #13 if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ 給的提示可以知道此行程式碼在檢測 *chunk 是否為 ASCII
#5 #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
- ((uint64_t)(b) & (0xff)) 保留所有 (b) 的 bits
- 與 0x0101010101010101u 相乘相當於將 (b) 每隔兩個 bit 在放值
- 假設 (b) = 0xb0 ，得 0xb0b0b0b0b0b0b0b0，因此 PACKED_BYTE(b) 將輸入做相同值的 padding
- 根據測驗一的結果，VV1 為 0x80
- 改成 #define PACKED_BYTE(b) ((uint64_t)(b) * 0x0101010101010101u)
從 strlower 函式觀察，#7 if (s[j] >= 'A' && s[j] <= 'Z') then s[j] ^= 1 << 5;
- 得知可透過 mask 0x20 (1 << 5) 與大寫字母做 XOR 轉成小寫字母
#17 *chunk ^= mask; ，*chunk 與 mask 做 XOR
- 因此當字母為大寫時，mask 得為 0x20
- 字母為小寫時，讓 mask 為 0x00 則可保留原 bit，保持小寫字母
觀察 A = *chunk + PACKED_BYTE(128 - 'A') 和 Z = *chunk + PACKED_BYTE(128 - 'Z')

char char + (128 - 'A') char + (128 - 'Z')

'A'(65) 128 103

'Z'(90) 153 128

'a'(97) 160 135

'z'(122) 185 160
- 當字母為 'a' ~ 'z' 時，其最高位的 bit 皆為 1 (>= 128)
- 而在字母為 'Z' 時，char + (128 - ‘Z’) 的結果也 >= 128
因此若想要透過 #16 uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; 來做出 0x00 或是 0x20 的 mask
- 可以先將 char + (128 - ‘Z’) 減1，使其最高位 bit 在大小寫字母不同時可以區別
char char + (128 - 'A') char + (128 - 'Z') - 1

'A'(65) 128 102

'Z'(90) 153 127

'a'(97) 160 134

'z'(122) 185 159
- char 在大寫時，(A ^ Z) 最高位為 1，小寫時為 0
- 再與 0x80 做 & 保留最高位 bit 後，進行右移 2 bit
- 因此當 char 大寫，0x80 >> 2 得 0x20，同理小寫 0x00 >> 2 得 0x00

char	char + (128 - 'A')	char + (128 - 'Z')
'A'(65)	128	103
'Z'(90)	153	128
'a'(97)	160	135
'z'(122)	185	160

char	char + (128 - 'A')	char + (128 - 'Z') - 1
'A'(65)	128	102
'Z'(90)	153	127
'a'(97)	160	134
'z'(122)	185	159

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

char str[] 更換為 char *str，會 Segmentation fault
規格書 6.4.5 String literals 提到

a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals.66) The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.

靜態配置足夠大的陣列空間存放每個字元

It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.

但是修改其內容是未定義的行為

char *str 是指向 string literal 的指標，如果對該指標變數操作則會直接更改到原 string literal 的內容，為未定義行為
而 char str[] 則配置新的字元陣列來存放與 string literal 相同的值，因此對其操作不會更改到原 string literal 的內容

What is the type of string literals in C and C++?

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











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

1. 解釋上述程式的原理

將整數看成數個獨立 bit，如 2 = 0b0010、3 = 0b0011
當一個數最多出現 2 次時，可以只用 1 bit 來描述，而當一個數最多出現 3 次時，則需要用 2 bit 來描述
- 00 表一個數未出現、01 表出現一次、10 表出現兩次
- 當出現三次時應為 11，但將其重置為 00 來表示該數已達上限，即該數不是要找的恰出現一次的數，因此給定一個數，其出現次數的規律為 00 -> 01 -> 10 -> 00
- 真值表如下，其中 high 表計數過程中的高位，low 表對應的低位，input 表下一個輸入， high' 和 low' 表對應的高低位輸出
  
  high low input high' low'
  
  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
- 最後一行當 high/low 狀態為 10 時，輸入 1 後輸出為 00 而非 11
- 高低位的邏輯表達式
  - $l o w = l o w \cdot \overset{―}{h i g h} \cdot \overset{―}{i n p u t} + \overset{―}{l o w} \cdot \overset{―}{h i g h} \cdot i n p u t$
    
    $= \overset{―}{h i g h} \cdot (l o w \cdot \overset{―}{i n p u t} + \overset{―}{l o w} \cdot i n p u t)$
    
    $= \overset{―}{h i g h} \cdot (l o w \oplus i n p u t)$
  - $h i g h = h i g h \cdot \overset{―}{l o w} \cdot \overset{―}{i n p u t} + \overset{―}{h i g h} \cdot l o w \cdot i n p u t$
- low' 即表示出現一次的整數，因為 0、2、3次對應的 low' 皆為 0，這也解釋為何要將 11重置為 00，避免兩種情形的 low' 為 1
利用上述式子計算 low' 和 high' 時，皆是沿用舊的 low 值，需要先暫存起來以待計算，嘗試修改真值表，避免用舊值計算
- 將先前真值表的 low' 輸出取代掉 low，即 low 的輸出重新作為輸入
  
  high low input high'
  
  0 0 0 0
  
  0 1 0 0
  
  1 0 0 1
  
  0 1 1 0
  
  0 0 1 1
  
  1 0 1 0
- 重新計算高位表達式
  
  $h i g h = h i g h \cdot \overset{―}{l o w} \cdot \overset{―}{i n p u t} + \overset{―}{h i g h} \cdot \overset{―}{l o w} \cdot i n p u t$
  
  $= \overset{―}{l o w} \cdot (h i g h \cdot \overset{―}{i n p u t} + \overset{―}{h i g h} \cdot i n p u t)$
  
  $= \overset{―}{l o w} \cdot (h i g h \oplus i n p u t)$
從上述得 KKK = ~higher，JJJ = ~lower

high	low	input	high'	low'
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

high	low	input	high'
0	0	0	0
0	1	0	0
1	0	0	1
0	1	1	0
0	0	1	1
1	0	1	0

[參考] https://blog.csdn.net/yutianzuijin/article/details/50597413

2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時

撰寫沿用舊 low 值的版本，額外宣告 tmp 變數暫存舊 low 值來計算 higher、lower










int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0, tmp = 0;
    for (int i = 0; i < numsSize; i++) {
        tmp = lower;
        lower = ~higher & (lower ^ nums[i]);
        higher = (higher & ~tmp & ~nums[i]) | (~higher & tmp & nums[i]);
    }
    return lower;
}

3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼

重複 4 次，用 3 個 bit 描述，000 -> 001 -> 010 -> 100 -> 000
重複 5 次，用 4 個 bit 描述，0000 -> 0001 -> 0010 -> 0100 -> 1000 -> 0000
重複 n 次，用 n-1 個 bit 描述
建真值表後計算邏輯表達式，撰寫程式碼

2020q3 Homework2 (quiz2)

tags: homework

測驗1

1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？

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

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

測驗2

1.解釋上述程式的運作原理

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

測驗3

1.解釋上述程式的原理

2. jemalloc

測驗4

測驗5

1.解釋上述程式的原理

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

測驗6

1. 解釋上述程式的原理

2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時

3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼

Read more

2020q3 Homework (quiz8)

Assignment3: SoftCPU

2020q3 Homework (quiz5)

Assignment2: RISC-V Toolchain

tags: `homework`