2020q3 Homework2 (quiz2)

contributed by < StevenChen8759 >

tags: linux2020

相關連結：
2020秋季進階電腦系統理論與實作 quiz2
2020秋季進階電腦系統理論與實作 quiz2 作業說明
2020秋季進階電腦系統理論與實作 quiz2 作業繳交區

---

測驗一

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

程式碼分析

• 函式透過第一個 while 迴圈，可一次比對字串中的八個字元是否為 ASCII charcater ，其原理是透過位元運算達成。
• 標準的 ASCII charcater 之範圍如下

Dec: 8'd0        to 8'd127
Bin: 8'b00000000 to 8'b01111111

• 因此，我們可透過 bitwise and 位元運算過濾非標準的 ASCII character
  • 不大於
    $127$ 的 char 值輸出全零。
  • 反之，則輸出非零。
  • 因
    $127$ 恰等於
    $2^{(8-1)}-1$，故大於
    $127$ 的數，其 最高位元 (MSB) 之值必為
    $1$ (以 char 型別而言)。
  • 因此我們將任意 char 與 0x80 做 bitwise and 運算，再檢查其值是否非零，即可確認該字元是否為標準 ASCII character
• 上述的運作原理只針對一個 char，在此處我們將其擴充成一次針對 8 個 char 操作，因此 uint64_t 的 bitwise and 操作，常數部分即替換成 0x8080_8080_8080_8080_8080_8080_8080_8080 進行操作，並透過 memcpy() 呼叫將字串中的 8 個字元內容複製至區域變數內。
• 第二個 while 迴圈則是針對長度非恰為 8 的倍數之字串檢查，其執行次數為 char length mod
  $8$。

改寫: 應用於檢知已知長度字串是否包含英文大小寫字母

• TODO

---

測驗二

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

程式碼分析

• letter 變數的主要目的在於指出引數 in 是否為字母，考量 return 的值加上了一個 and mask，其值為 0x0F，根據 ASCII 數字表示法的特性，我們不須再將回傳值加上 shift 偏移值，即可代表 數字 0 ~ 9。
  • 根據以上分析，此 case 中的 shift 值應為 0
  • 因此，變數 in 的 and mask 應選擇 0x40，在輸入非字母的情況下，使 shift 值為 0。
  • 根據上述的分析，在 in 值輸入字母(不分大小寫)時，letter 的值為 0x40
• 而 shift 變數的主要作用在於 in 為字母輸入時加上一個 offset，使 return (in + shfit) 的最低四個位元對應到0x00 ~ 0x0F，並透過 and mask 值 0x0F 令最高四位元的值為 0。
  • 因此，in 輸入為字母時，shift 值應為 9。
  • 因為 A / a 對應 0x41 / 0x61，故 in + 9 後即為 0x4A / 0x6A，加上 and mask 值 0x0F，即得正確回傳值 10 (decimal)
  • 其餘 B / b 至 F / f 之對應亦同。
• 參考下列的數值對應，可理解 shift 初值指派的右移值原理。

  8'b01000000 <= letter
------------------------------
  8'b00001000 <= letter >> 3
| 8'b00000001 <= letter >> 6
------------------------------
  8'b00001001 <= shift

擴充: 十六進制字串輸入與轉換

• TODO

---

測驗三、四

測驗三程式碼與分析

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFF_FFFF_FFFF_FFFF) / (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 位元的整數，並結合定點數的概念，將低 64 位元視為小數，高 64 位元視為整數。
• 除法原理公式:
  $n=q\cdot d+m$
  • 移項除法原理公式:
    $\frac{n}{d}=q+\frac{m}{d}$
• 根據公式
  $\frac{n}{d}=n\cdot \frac{2^{64}}{d}\cdot \frac{1}{2^{64}}=q+\frac{m}{d}$
• 移項得
  $q=n\cdot \frac{2^{64}}{d}\cdot \frac{1}{2^{64}}-\frac{m}{d}$
• 因
  $m<d$，且在，故上述公式在二進位計算下可簡化成
  $q=n\cdot \frac{2^{64}}{d}\cdot \frac{1}{2^{64}}$
• 我們接著計算
  $\frac{2^{64}}{d}$ ，也就是 Macro M 的部份。
  • 因數值
    $2^{64}$ 需要 65 位元才能表示，且因　
    $2^{64}$ 與　
    $2^{64}-1$ 除以 3 皆有精確度不足的狀況，因此我們使用
    $\frac{2^{64}-1}{d}$ 代替。
  • 也因為精確度不足的問題，不論是使用
    $2^{64}$ 與　
    $2^{64}-1$ ，在輸入數字恰好整除時，((__uint128_t) M * n) >> 64 所計算的 quotient 將會與實際值恰好差 1。(參考下述分析)
  • 因此，我們在 Macro M 中的
    $\frac{2^{64}-1}{d}$ 項後面再加上 1 補償誤差，即可解決。(參考下述分析)
• 變數 quotient 已重現了上述
  $\frac{n}{d}=n\cdot \frac{2^{64}}{d}\cdot \frac{1}{2^{64}}$ 的較快版本，
  $n$ 乘上 Macro M 所計算的常數後，右移 64 位元，即可得到商數。
• 最後，透過除法原理公式的移項，回傳 n 的餘數。
  • 即
    $m=n-q\cdot d$

這方面的描述不太確定數值會恰好差 1 的原因，希望老師可以在指點方向修改成正確且精準的描述，謝謝老師~

考慮到 underflow 了嗎？

jserv

謝謝老師指點，經過一番思考後終於找出原因，但在研讀 IEEE 754 Standard 的 underflow 描述後，個人認為使用 定點數精確度不足 描述此一狀況較為精準，再麻煩老師分析，謝謝老師~

分析：定點數精確度不足與補償

• 我們在上述使用
  $\frac{2^{64}-1}{d}$ 時，與原式表示值會有誤差，這是因為定點數可能會遇到無法精確表示小數的狀況 (像是
  ${\displaystyle \frac{1}{3}}$)，考量下列的算式：
  • 理想：
    ${\displaystyle \frac{1}{3}}={\displaystyle \frac{1}{4}}+{\displaystyle \frac{1}{16}}+{\displaystyle \frac{1}{256}}+...=\sum _{i=1}^{\mathrm{\infty }}{\displaystyle \frac{1}{4^i}}$
  • 實際：
    ${\displaystyle \frac{1}{3}}\approx \sum _{i=1}^{N/2}{\displaystyle \frac{1}{4^i}}$，其中
    $N$ 為定點數中小數部份的表示位元數
• 上述實際狀況的算式在左右兩邊乘以三之後，使用二進位表示之值明顯會小於 1，在只保留定點數中整數部份的情況下，即造成了 quotient 與實際值相差 1 之情形。
• 我們假設使用 16 位元表示一個定點數，整數與小數部份各佔用 8 個位元，參考下列
  $\frac{1}{3}\cdot 3$ 的操作：

origin: 16'h0055 => 16'h00FF

• 因此，我們在小數點末位 +1 補償，即可得到正確的結果, 且不影響不可被 3 整除的數字輸出之商。

add_1:  16'h0056 => 16'h0100

測驗四程式碼與分析

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFF_FFFF_FFFF_FFFF) / (D) + 1))

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

• 根據上述精度的分析, 我們代入數個 n 值解析輸出結果：

"1 * M" : 64'h5555_5555_5555_5556
"2 * M" : 64'hAAAA_AAAA_AAAA_AAAC
"3 * M" : 64'h0000_0000_0000_0002
_
"M"     : 64'h5555_5555_5555_5556
"M - 1" : 64'h5555_5555_5555_5555
_
"4 * M" : 64'h5555_5555_5555_5558
"4 * M" : 64'hAAAA_AAAA_AAAA_AAAE
"6 * M" : 64'h0000_0000_0000_0004

• 根據上述的演示，當輸入的 n 可整除時，因定點數的整數部份須 128 位元才能表示，因此此處 64 位元即為定點數的小數部份，且因 n 整除時其定點數的小數部份趨近於 0 (此處僅考慮以二進位表示)，其值必定小於 M, 故可以此作為判斷是否整除的依據。
• 再考量輸入值為 1 的狀況，此時因比較運算子為 <= ，故代入 M 會造成錯誤的輸出，故我們須採用 M - 1 表示，才能正確判斷是否整除。

---

測驗五

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

程式碼分析

• 大寫轉成小寫的位元運算方法為：char ^ 0x40，因此當輸入值須轉換成小寫時，mask 之值應為 0x40 ；否則為 0x00 ，即保留原始字元之值。
  • mask 初始值指派時，前面的運算結果右移了兩個位元，綜合上述的想法，VV4 之值應為 0x80。
• 根據原題目已給定的程式碼，(A ^ Z) 為判斷輸入字元是否在 A 到 Z 的範圍內。
  • XOR 運算的特性為 同0異1， 即兩輸入位元相同則輸出0，兩輸入位元相異則輸出1。
  • 根據這樣的特性, 我們期望透過 XOR 運算，在輸入為大寫英文字母時輸出 1，否則輸出 0 ；以符合上述的轉換規則。
• 再接著看到變數 A 與 Z 的初始值指派，我們透過下列表格搭配位元運算特性，推論 VV2 與 VV3 之值:

輸入字元	變數 A 之值	變數 Z 之值	mask 之 MSB
(0x40)	127 + VV2	102 + VV3	0
A(0x41)	128 + VV2	103 + VV3	1
Z(0x5A)	153 + VV2	128 + VV3	1
(0x5B)	154 + VV2	129 + VV3	0
a(0x61)	160 + VV2	135 + VV3	0
z(0x7A)	185 + VV2	160 + VV3	0

• 參考 0x40 的輸入，其 mask 之 MSB 值應為 0，故 VV2 必非正值。
• 參考 A 的輸入，其 mask 之 MSB 值應為 1，因此 VV2 必不可能為負值，故 VV2 必為 0。
• 參考 Z 的輸入，其 mask 之 MSB 值應為 1，此時僅有令 VV3 -1，才能同時令輸入 Z 時為 1，且輸入 0x5B 時輸出為 0；故 VV3 必為 -1。
• 參考測驗一中 Standard ASCII 之位元運算判定方法，VV1 之值應為 0x80。

String Literal 議題探討

• char *str = "xxxx"　的宣告方式會將字串視為 String Literal 並儲存在 code section，對此 String Literal 進行寫入操作是 未定義行為 (Undefined Behavior)，進而造成 Segmentation Fault。
• 因此在宣告的時候須使用陣列配置或是動態記憶體配置的方法，才能順利將字串中的大寫字元轉換成小寫。
• Ref: 你所不知道的C語言：指標篇 - 重新探討「字串」

---

測驗六

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

程式碼分析

• TODO