# 2020q3 Homework2 (quiz2)
contributed by < `erickuo5124` >
###### tags: `2020進階電腦系統理論與實作`
---
## 測驗`1`
目前電腦中用得最廣泛的字元集及其編碼，是由美國國家標準局(ANSI)制定的ASCII碼，這些碼可以排列成一個十進位序號0～127。所以，7 位ASCII碼是用七位元二進位數字進行編碼的，可以表示128個字元。
:::warning
在電腦的存儲單元中，一個ASCII碼值占一個位元組(8個二進位位元)，其最高位元(b7)用作奇偶校驗位。
:::
下面的程式碼式用來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元，且一次比對 64 位元的資料 (word size):
```c=
#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;
}
```
一開始處理 `size` 為 0 的情況。進到第一個 while 迴圈之後，一次處理 8 個字元 (一個字元為 8 bits， 8 * 8 = 64)，並使用 `memcpy` 將資料複製到 `payload` 裡面。接著用 0x8080808080808080 對它作 `AND` (0x80 的值是 $10000000_2$ ， ASCII 字元理應不超過 127) ，若是有 0 以外的值就回傳 false。
e.g.
$$
\ \ \ \ \ \ \ \ \ \ \ \ 10000000_2\\
\frac{AND\ \ 10100110_2}{\ \ \ \ \ \ \ \ \ \ \ \ 10000000_2}
$$
第二個 while 迴圈則處理不滿 8 個字元的情況。
:::success
延伸問題:
1. 為了提升程式效能，並考慮到 data alignment ，使用 `memcpy` 複製指定長度的資料。
2. 必須判斷是否在 `'A'-'Z'` 或 `'a'-'z'` 間，類似測驗`5`，因此將部份程式碼來改寫：
```c=
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
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);
uint64_t A = *payload + PACKED_BYTE(128 - 'A');
uint64_t Z = *payload + PACKED_BYTE(128 - 'Z' - 1);
uint64_t a = *payload + PACKED_BYTE(128 - 'a');
uint64_t z = *payload + PACKED_BYTE(128 - 'z' - 1);
uint64_t mask = ((A ^ Z) | (a ^ z)) & PACKED_BYTE(0x80);
if(mask ^ PACKED_BYTE(0x80))
return false;
i += 8;
}
while (i < size) {
if (str[i] < 65 || (str[i] > 90 && str[i] < 97) || str[i] > 122)
return false;
i++;
}
return true;
}
```
:::
參考資料
* [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
* [ASCII 碼介紹](http://kevin.hwai.edu.tw/~kevin/material/JAVA/Sample2016/ASCII.htm)
---
## 測驗`2`
下面程式碼會將十六進位的字串轉為數值
```c=
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
```
第 3 行的 `letter` 用來判斷 `in` 是否為英文字母， 又第 7 個 bit 為英文字母都有而數字沒有的，因此選 0x40。
因為英文字母的後面 4 bit 剛好跟數值差 9 ，因此第 2 行的 `shift` 將第 7 個 bit 分別移到 1 跟 4 的位置。若 `letter` 有值， `shift` 會為 9 (0000 1001)
ex:
- `'A'`: 0100==0001==
- `'C'`: 0100==0011==
數字的後面 4 bit 則剛好為其數值，且不是字母 `letter` 會為 0， `shift` 也會為 0
ex:
- `'1'`: 0011==0001==
- `'6'`: 0011==0110==
第 5 行則將結果加上原本的數值，並傳後面 4 bit 回去
:::success
延伸問題:
1. 利用 acsii 中相對應的位置，找出字元的特性，利用 bitwise 操作讓實作達到不需要使用分支
2.
:::
---
## 測驗`3`
下方程式碼實作取餘數 (除數為 3)，並用乘法來代替除法運算，減少運算成本
原理：
$$
\frac{n}{d}=n\times\frac{\frac{2^N}{d}}{2^N}
$$
當 $d$ (除數) 的數值是已知的狀況下，就可以先計算$\frac{2^N}{d}$，將它轉換為乘法和位移操作
```c=
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;
}
```
第 7 行即為上面所提到的乘法及位移操作，其中的 `M` 先使用預處理器完成，乘上 `n` 之後向右移 64 位元，因此可以知道本題的 $N$ 為 64
:::warning
`M` 在預處理器那邊所使用的算式並非 $\frac{2^N}{d}$ ，而是 $\frac{2^N-1}{d}+1$ ，因為這裡考量到了並非所有 $d$ 都能整除，且：
$$
\frac{2^N}{d}=\lfloor\frac{2^N}{d}\rfloor\\
\frac{2^N-1}{d}+1=\lceil\frac{2^N}{d}\rceil
$$
這裡的實作選擇後者將差值補償回去 (不過我不知道為什麼:joy:)
:::
最後用 $被除數-商\times除數$ 得到餘數
:::success
延伸問題:
1. **除數已知的情況下**，對它做預處理之後可將除法轉換成乘法及位移運算，如此可有效降低運算成本
2.
:::
---
## 測驗`4`
```c=
bool divisible(uint32_t n)
{
return n * M <= M - 1;
}
```
- $n\times M = n\times \lceil\frac{2^N}{d}\rceil$ => $\frac{n}{d}$ 的小數部份
- $M-1 = \lfloor\frac{2^N}{d}\rfloor$ => $\frac{1}{d}$ 的小數部份
沒有餘數的情況只會是當 $n=0$ 或 $n=d$ ，其他狀況下 $\frac{n}{d}$ 皆會大於等於 $\frac{1}{d}$ ，因此選擇 `M-1`
---
## 測驗`5`
下面的程式碼將字串內所有大寫字母轉換成小寫字母，且一次對 64 位元的資料進行操作
```c=
#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(b)` 可以將輸入 `b` 擴充成重複 8 次的 64 位元無號整數
第 13 行為判斷該 `chunk` 是否在 ascii 的範圍內，因此會對 `PACKED_BYTE(0x80)` 做 AND 運算
先看第 16 行， `mask` 對 `A^Z` 跟 `PACKED_BYTE(0x80)` 做 AND ，可以知道重點應該著重在每個資料的最高位。
那再往回看到 14, 15 行， `uint64_t A` 在字元大於等於 `'A'` 的時候， MSB 會是 1； `uint64_t Z` 則是在字元小於等於 `'Z'` 的時候， MSB 會是 0。
如此一來，若該字元在 `'A'` 到 `'Z'` 之間時， `A^Z` 的值將會是 0x80 ，作 AND 運算之後往右移的結果會是 0x20 。又大寫字母對 0x20 作 XOR 會得到小寫的字母，即：
$$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0100\ 0001_2(A)\\
\frac{XOR\ \ 0010\ 0000_2}
{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0110\ 00001_2(a)}
$$
:::success
延伸問題：
1. 利用 `PACKED_BYTE` 擴充每次做運算的長度，並用 bitwise opration 來判斷是否在範圍內，進而達到增加程式效率
2.
:::
參考資料
* [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
---
## 測驗`6`
下面的程式碼用來找出陣列中指出現一次的元素
```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;
}
```
$XOR$ 的**交換律**在此可以允許輸入不須按照順序，即:
$$
a\oplus b\oplus c = a\oplus c\oplus b
$$
**歸零律**則讓它有儲存的功能，即：
$$
a\oplus a = 0
$$
而因為除了那個指出現一次的元素之外，其他的元素均會出現 3 次，因此這裡使用了 `higher` 跟 `lower` 來儲存。若存在 `lower` 中，則代表第一次出現；若存在 `higher` 中，則代表出現第 2 次；第三次出現的話會把兩邊都消除掉。
第 6 行會在第三次出現時將它清除掉，選 `~higher`
第 7 行則是檢查是否出現第 2 次，選 `~lower`
Sign in with Wallet
Connect another wallet