# 2020q3 Homework2 (quiz2)
contributed by < `Weiting0114` >
> [測驗題目](https://hackmd.io/@sysprog/2020-quiz2)

## Test1
* ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
* 二進位表示 0~127 為 `0000 0000`~`0111 1111` ，因此只要第 8 個 bit 為 1 ，該欄位便不為有效的 ASCII 字元。
* 因此，我們可以利用 bitwise 操作，判別第 8 個 bit 是否為 0。

>1個 char 的大小 = 1 byte = 8 bits
>
>0x80 = (1000 0000)~2~

### 版本一：逐字比較

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

* 參數
1. <span class="blue">const char</span> str[]：該字串第一個字元的記憶體地址，而 `const` 為 constant 的縮寫，表示恆常不變的數值。
2. `size_t` 真實型別與作業系統有關，在64位元中為 long long unsigned int，非64位系統中為 long unsigned int。

* 程式
1. `str[i]` 為該字串的第一個字，每個英文字母可以透過 ASCII 轉成一組對應的二進制，故可以用來和0x80做運算。
>範例：char str[] = "Hello" ， str[1] = 'H'

2. 為何使用 <span class="red">`0x80`</span> ？
<span class="red">`0x80`</span> 為(`80`)~16~ 也相等於 (`1000 0000`)~2~，所以將 `str[i]` 與 (`1000 0000`)~2~ 做 `AND` 運算即可得知 `str[i]` 是否為有效的 ASCII 字元。

> 假設比對 "H" 是否屬於 ASCII，我們知道 "H" 轉為數字對應到 (`0x48`)~16~ = (`0100 1000`)~2~。 再來做 **(`1000 0000`)~2~ AND (`0100 1000`)~2~**
> 0x80 ： 1000 0000
> 0x41 ： 0100 0001
> AND結果：0000 0000
> 所以 return true， "H" 為 ASCII

3. 由於此版本是每個字元逐一比對，效率較低，為了改善這個問題，在第二個版本嘗試一次比對 64 位元的資料。

**在 64 位元的架構下，嘗試一次比對 64 位元的資料 (即 word size)**

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

* **運作原理 :**

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

* 如果比較的字串大於或等於一個 word (假設 word size = 8 bytes = 64 bits) 則一次將一個 word 大小的資料拷貝進 payload 變數。
* 對於 payload 變數中的每一個 byte ，如果值 >= 128 (0x80) 則不屬於 ascii。

while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }

* 剩餘不滿一個 word 的資料則一次一個 byte 將剩餘的資料判斷完畢。

### 延伸問題
::::info
1.為何特別用到 memcpy 呢？
::::

* 查看 memcpy 在 [glibc](https://reurl.cc/Q3mlaZ) 中的原始碼發現不但使用記憶體長度直接比較之外，還有執行對齊的處理，讓執行更有效率。

## Test2
#### 題目解析：
定義一函式，可將輸入的十六進位表示字元 0~9, a~f or A~F，轉換為十進位數值 0~15。

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

根據題目中引述：
> 以下摘自 ASCII 表格
>* '0', '1', '2', …, '9' 對應到 0x30, 0x31, 0x32, … 0x39
>* 'a', 'b', 'c', …, 'f' (小寫) 對應到 0x61, 0x62, 0x63, …, 0x66
>* 'A', 'B', 'C', …, 'F' 對應到 0x41, 0x42, 0x43, …, 0x46

從下列表格可以發現，數字和字母的差異位於 b~6~，數字 b~6~ 為 0 ， 數字 b~6~ 為 0。
| char | 二進制(b~7~b~6~b~5~b~4~ b~3~b~2~b~1~b~0~) |
| ---- |:--------------:|
| 0 | (0011 0000)~2~ |
| 5 | (0011 0101)~2~ |
| 9 | (0011 1001)~2~ |
| A | (0100 0001)~2~ |
| a | (0110 0001)~2~ |
| F | (0100 0110)~2~ |
| f | (0110 0110)~2~ |

const uint8_t letter = in & MASK;

因此此處 **MASK** 應選擇 `(c) 0x40`，
將該位元分離出來，判斷目前輸入的字元是英文抑或是數字。

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

>同樣從上述表格中可發現，若僅看 b~3~b~2~b~1~b~0~ 四個位元，
'0' ~ '9' 可直接對應到數值 0 ~ 9，
'a' ~ 'f' 和 'A' ~ 'F' 則是直接對應到數值 1 ~ 6，距離題目要求的數值須再加 9。

因此此處的 `shift` 變數則是使其若為數字時為 0，英文字母則為 9 作為偏移量，故
**AAA 選擇 `(a) 3`**，將字母特有左二的 1 移至右四變為 (0000 1000)~2~
**BBB 選擇 `(b) 6`**，將字母特有左二的 1 移至右一變為 (0000 0001)~2~
再進行 Bitwise OR 運算變成 (0000 1001)~2~，即為位移量 9 (若為數字則會是 (0000 0000)~2~ )。

    return (in + shift) & 0xf;

最後將輸入字元加上該位移量，並與 `0xf` 做 Bitwise AND 運算取右四位元，結果即會符合函式需求。

## Test3
## Test4
## Test5
## Test6

<style>
.blue {
color: #33A3FF ;
}
.red{
color: #BE1221;
}
</style>