2020q3 Homework2 (quiz2)

contributed by < ccs100203 >

tags: `linux2020`

2020q3 第 2 週測驗題

TODO 一些延伸問題

測驗 1

從題目敘述得知，7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
而 0x80 為 1000 0000，所以當以下成立時，代表 str 已經超過 ASCII 的範圍了。

if (str[i] & 0x80)
    return false;

題目要我們在 64 位元的架構下，嘗試一次比對 64 位元的資料 (即 word size)，從上面的例子可以推斷出每個 byte 都要與 0x80 做比較，所以在第 4 行填入 0x8080808080808080







while ((i + 8) <= size) {
    uint64_t payload;
    memcpy(&payload, str + i, 8);
    if (payload & 0x8080808080808080)
        return false;
    i += 8;
}

延伸問題

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

題目敘述說一次要比對 64 bits

while ((i + 8) <= size)

藉由 i+8 去移動，會一次比對 8 bytes，如果 if 為 true 則代表有找到不符合的，就會直接 return false

while (i < size)

如果剩餘的無法一次比對 64 bits，那麼就會回歸為比較一個 byte

參考記憶體管理、對齊及硬體特性
memcpy 的用途為 data alignment，e.g. 至少抓 1 byte，如果不對齊資料，會導致 cpu 的存取因 address 不是在 4 的倍數上而變慢。而現代 x86 處理器允許 data unalignment

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

TODO

測驗 2

這題的 function 為一個 parser，給定的條件為

hexchar2val(a~f) return 10~15
hexchar2val(A~F) return 10~15
hexchar2val(0~9) return 0~9

當我們從二進位的時候可以簡單地看出答案，所以先用二進位表示

Example	1	2	3	4	5	6
F	1	0	0	0	1	1
f	1	1	0	0	1	1
8	0	1	1	1	0	0






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

觀察以上程式碼，會發現 shift 是遇到英文字母的時候才會使用到的，因為第 5 行做 (in + shift) & 0xf 後只會保留右邊的 4 個 bits，而 0~9 在一開始的右邊 4 個 bits 就已經是答案了，所以沒有必要多做操作
這樣就可以知道 MASK 是要分辨出字母與數字，從 column 1 就可以分辨出兩者，所以 MASK 為 0x40
如果是字母，做完第 3 行後會得到 0x40 ( 0100 0000 )，因為最後是 (in + shift) ，推敲出字母都與所需的數字差 9， e.g. f 為 0110，但是答案需要輸出 15。這樣我們只要把 shift 變成 9 就好了
因為 9 等於 1001，所以 letter >> 3 | (letter >> 6) 就是我們要的答案，下面是完整的程式碼

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

延伸問題:

很直接的先把 input 改為 pointer 來處理多個 char，再修改下面的第 14 行，把每個數值轉換過後再乘上對應的

16^{n}

，這邊用 shift 去代替乘法。


























#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

uint64_t hexchar2val(uint8_t* in)
{
    int len = strlen(in);
    uint32_t ans = 0;
    for (int i = 0; i < len; i++)
    {
        const uint8_t letter = in[i] & 0x40;
        const uint8_t shift = (letter >> 3) | (letter >> 6);
        ans |= ((in[i] + shift) & 0xf) << (4 * (len - i - 1));
    }
    return ans;
}

int main(){
    u_int8_t* c1 = "0FF1CE";
    u_int8_t* c2 = "FEE1DEAD";
    u_int8_t* c3 = "FFBADD11";
    u_int32_t a = hexchar2val(c3);
    printf("%u\n", a);
    return 0;
}

測驗 3

將除法改為乘法運算

為了將除法轉換為

預先計算的
$\frac{2^{N}}{d}$
乘法
shift

使用

\frac{n}{D} = n * \frac{\frac{2^{N}}{D}}{2^{N}}








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

第 2 行的 M，就是為了預先計算

\frac{2^{N}}{D}

，這時我們不知道應該要填多少。所以繼續往下，看到第 6 行，這邊就是要算

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

，我們把他轉換為

M * n / 2^{64}

，這時候就很容易看出

2^{N}

即為

2^{64}

，那麼為什麼是選擇 0xFFFFFFFFFFFFFFFF 呢，因為已經 overflow 了，所以索性 -1，再從後面的 +1 做無條件進位補回來，第 6 行的 shift 是無條件捨去，也能補回誤差。這樣我們就得到 quotient 了，於是就能在第 7 行得到餘數。

延伸問題:

TODO

測驗 4

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

因為沿用 D 跟 M，D = 3, M = 0x55…56，所以
左邊會是 n * (0x5555555555555555 + 1)
右邊會是 0x5555555555555555
我把 n 轉換為 3k、3k+1、3k+2 這三種情況

3k * (0x5555555555555555 + 1) = (0xff…ff + 3) * k = (0 + 2) * k = 2k
(3k + 1) * (0x5555555555555555 + 1) = 2k + 0x55…56 = 2k + M
(3k + 2) * (0x5555555555555555 + 1) = 2k + 0x55…56 * 2 = 2k + 2M

由於 n 是 unsigned 32 bits，所以 n >= M 不可能發生，只有 2k 會 <= M - 1，可以得知 n 在拆成 3k 的時候才能符合判斷式 n * M <= M - 1，故可判斷是否為 3 的倍數

測驗 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(0x80)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1));
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

PACKED_BYTE 的用處是把最小的兩個 bytes 補滿 64 bits，
e.g. PACKED_BYTE(0x80) 會得到 0x8080808080808080

因為單純看程式碼實在推敲不出答案，所以我直接執行程式，來推敲原因

PACKED_BYTE(128 - 'A' + 0) = 0x3f…3f
PACKED_BYTE(128 - 'Z' + (-1)) = 0x25…25

printf("%ld, %lx, %lx, %lx\n", i, A, Z, mask);

input "This eBo"
output: 0, ae81a45fb2a8a793, 94678a45988e8d79, 20000000000020

藍色是程式第 14~15 行的 A 跟 Z，綠色是 ASCII 內的字母

	1	2	3	4	5	6	7 LSB
A	0	1	1	1	1	1	1
Z	0	1	0	0	1	0	1
a	1	1	0	0	0	0	1
z	1	1	1	1	0	1	0
A	1	0	0	0	0	0	1
Z	1	0	1	1	0	1	0

可以看出大寫的時候會出現 2，從上面的表看出 0x20 在 ASCII 上剛好可以把大寫轉換為小寫，所以這個 mask 的用處很明顯就是要找出需要轉換為小寫的 char，並且在第 17 行 *chunk ^= mask 把他轉換為小寫，而小寫字母就保留原樣。 (與 1 做 xor 是 toggle)
而會是 2 的原因是因為往右 shift 2，所以原本是 8，而這個 8 很明顯是從第 16 行 ((A ^ Z) & PACKED_BYTE(0x80)) 來的，從第 1 點我們知道大寫的時候應該要產生 0x80，小寫會是 0x00，所以接下來要推斷 A^Z 如何在 MSB 產生 1 或 0。
大寫字母需要在 A^Z 的 MSB 產生 1，所以需要各一個 0 跟 1，而小寫字母則是需要兩個 0 或 1，程式內的 (128 - 'A' + 0) 跟 (128 - 'Z' + (-1)) 相減得到 26，剛好可以容納下所有英文字母，嘗試 0x25 與 A~Z 相加可以發現最大是 0x7F 剛好會保持 MSB 為 0，而從 0x3F 加的話，就會從 0X80 開始，MSB 肯定是 1，於是 (A ^ Z) 過後的 MSB 就會得到 1。
如果是小寫字母，無論如何我們都會得到大於 0x80 的數字，所以 A 跟 Z 的 MSB 都會是 1，(A ^ Z) 過後的 MSB 就會得到 0，在 mask 的地方就會產生 0。
這樣就釐清為什麼程式會是這樣設計了，VV1 選 0x80 是為了驗證是否屬於 ASCII，VV2 選 0 是為了讓大寫的字母相加後的 MSB 一定是 1，VV3 選 -1 是因為需要多 -1 才能夠容納 26 個英文字母 (原本只相差 25)，VV4 選 0x80 是為了讓 mask 只保留需要轉換為小寫的 MSB，並將他 shift 到 0x20 的位置。

延伸問題

char str[] 就如同一般的 array 一樣，可以對他做任何的操作。但 char *str 是 string literal，屬於 read-only part of memory，任何想要對他們的修改都會變成 undefined behavior。由於題目的程式是 in-place 的演算法，所以不能夠用 char*

測驗 6

這題為 LeetCode 137. Single Number II，要找出只出現過一次的 value，而其他的 value 都會出現 3 次

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

在解這題前我想要先解釋如果其他 value 是出現 2 次的情況
由於 xor 的特性可以簡單的寫出下面的 code，當相同的 bit 出現兩次時，就會被清空成 0，最後就只會留下出現一次的 value 的 bits

int singleNumber_even(int* nums, int numsSize){
    int a = 0;
    for(int i=0; i<numsSize; ++i)
        a ^= nums[i];
    return a;
}

回到這題，由於其他 value 會出現三次，所以使用兩個變數去紀錄，第一次出現時會存到 lower 裡，第二次會把他放到 higher，第三次就會把他從 higher 移除，這樣全部做完時就會在 lower 得到想要的 number，看下面的 code:

第 5 行會將 num 放進去 lower 裡面，但是如果 num 已經在裡面，就會把他移除，代表他已經出現第二次
第 6 行我們只會將第一次出現的 num 放進去 lower，所以如果在 higher 裡就會被移除，這樣可以檢測他是否為第三次出現
第 7~8 行 higher 紀錄的是第二次出現的 num，所以當這個 num 是第一次出現時，會因為 num 在 lower 裡面也有，而藉由第 8 行把 higher 內的 num 清除。第二次遇到時就會直接放入 higher，第三次遇到時就會因為已經存在 higher 內而藉由第 7 行清除掉，換句話說，higher 最後會是 0











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

延伸問題

其實就是一直增加變數去紀錄

將程式推廣成 3、4、5… 次
1. 如果是偶數次的話，直接使用上面的如果是 2 次的情況就好，因為 xor 的特性每兩次就會清空一次，所以只要是偶數次都可以使用
2. 奇數次就需要增加變數去紀錄 //todo

2020q3 Homework2 (quiz2)

tags: linux2020

測驗 1

延伸問題

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

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

測驗 2

延伸問題:

測驗 3

延伸問題:

測驗 4

測驗 5

延伸問題

測驗 6

延伸問題

Read more

2022/08/23~24 OSSLA Records

So What Has RCU Done Lately? (2023)

2021q1 Homework5 (sort)

RCU in the Linux Kernel

tags: `linux2020`