---
# System prepended metadata

title: 2020q3 Homework2 (quiz2)
tags: [sysprog2020]

---

---
tags: sysprog2020
---
# 2020q3 Homework2 (quiz2)
contributed by < `nickchenchj` >

## Prerequisite
* [problems for quiz2 (2020q3)](https://hackmd.io/@sysprog/2020-quiz2)

## Problem 1
### Required Functions
* Check if the input string is in ASCII
* Process 64 bits at once (8 chars)

### Code Snippets
* `is_ascii` (8-bit version)
```c=
#include <stdbool.h>
#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;
}
```

* `is_ascii` (64-bit version)
```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;
    /* Processes 8 chars at once in each iteration */
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }
    /* Processes the remaining chars one by one */
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}
```

#### MMM = ?
* `(a)` `0x0080008000800080`
* `(b)` `0x8000800080008000`
* `(c)` `0x0808080808080808`
* `(d)` `0x8080808080808080`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`

### How `is_ascii` (8-bit version) works?

| Base |         ASCII         |    Extended ASCII     |
|:----:|:---------------------:|:---------------------:|
|  2   | 0000 0000 ~ 0111 1111 | 1000 0000 ~ 1111 1111 |
|  16  |      0x00 ~ 0x7F      |      0x80 ~ 0xFF      |

:::info
:bulb: From the table, we can find that the [MSB](https://en.wikipedia.org/wiki/Bit_numbering#Most_significant_bit) of the char in ASCII is always `0` (binary), and that of the char in extended ASCII is always `1` (binary). 
:::

* to extract the value of the 8th bit, apply `str[i] & 0x80`:

|      Type      |  str[i]   | str[i] & 0x80 | Result  |
|:--------------:|:---------:|:-------------:|:-------:|
|     ASCII      | 0100 0011 | ==0==000 0000 |   `0`   |
| extended ASCII | 1100 0011 | ==1==000 0000 | not `0` |

###### Note: `0100 0011` and `1100 0011` were just examples for this demonstration

* after filtering, all bit values except for the [MSB](https://en.wikipedia.org/wiki/Bit_numbering#Most_significant_bit) were set to `0`, and the value of MSB remained unchanged
* from the result, all we need to do is to check whether the result is `0` or not
* if the result is `0`, then the char is in ASCII

### How `is_ascii` (64-bit version) works?
* similarly, we can apply the same method to `is_ascii` (64-bit version)
* we simply extend `0x80` to `0x8080808080808080` and perform bitwise AND on the input string (8 chars at once) until the result is non-zero or less than 8 chars remain
* by doing so, if the result of bitwise AND is `0`, it means that the 8 chars are all in ASCII
* if there are less than 8 chars remain in the input string, process them with `is_ascii` (8-bit version)

:::success
Answer: `(d)` `0x8080808080808080`
:::

<!-- ### Why `memcpy`?

### Advanced Applications
#### Example 1
A function that can check if a string of known length contains letters

#### Example 2
A function that can check if an input string doesn't contain any invalid characters
 -->

## Problem 2
:::info
打英文好累，我還是乖乖打中文
:::
### Required Functions
* 將十六進為表示的字元轉為數值 (case insensitive)
* e.g.
    * `0` => 0
    * `1` => 1
    * `A`, `a` => 10
    * `F`, `f` => 15


### Code Snippets
* `hexchar2val`
```c=
uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}
```

#### MASK = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`

#### AAA = ?
* `(a)` 3
* `(b)` 2
* `(c)` 1
* `(d)` 0

#### BBB = ?
* `(a)` 7
* `(b)` 6
* `(c)` 5
* `(d)` 4

### 解題思路
:::info
以下摘自 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`
:::

* 首先考慮數字 `'0'`~`'9'`, 僅需將 `0x3X` 的 `3` 過濾掉即可得到正確數值
* 再來考慮英文的大小寫，可以由上方提供的資訊看出 `'a'` 與 `'A'` 都是從 `0xX1` 開始，而我們期望 `'a'` 與 `'A'` 的值都變成 10，因此需要做的事情就是先將 `'a'` 與 `'A'` 轉換成 `0x01` 再加上 9 (`0000 1001`) 即可得到期望的數值 (適用於所有英文字元)
* 那麼要如何取得 9 (`0000 1001`) 呢? 這時需要運用 bitwise AND 的技巧得到英文字元的特徵，同時也必須過濾掉數字 `'0'`~`'9'` 的特徵 (`0x3X` 的 `3`)


| 字元  | 二進位表示 | 過濾後 (letter) |
|:-----:|:----------:|:---------------:|
| `'1'` | 0011 0001  |  0==0==00 0000  |
|  `'a'`  | 0110 0001  |  0==1==00 0000  |
|  `'A'`  | 0100 0001  |  0==1==00 0000  |

* 根據上面的表格來推斷，只要將字元和 `0100 0000` 做 bitwise AND 之後就可以萃取出左邊第二個 bit 的值，因此可以得知 `MASK` = `0x40` (`0100 0000`)
* 上面有提到，將英文字元轉換成值的時候需要加上 9 (`0000 1001`)，這時只要運算 `shift = (letter >> 3) | (letter >> 6)` 就可獲得我們想要的值


|           字元           |   shift   |
|:------------------------:|:---------:|
|       `'0'`~`'9'`        | 0000 0000 |
| `'a'`~`'z'`, `'A'`~`'Z'` | 0000 1001 |

* 最後用 `(in + shift) & 0xf` 取得最小的 4 個位元就是答案了!

:::success
Answer:
MASK = `0x40`
AAA = 3
BBB = 6
:::

## Problem 3
### Required Functions
* 快速取餘數

### Code Snippets
* `quickmod`
```c=
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;
}
```

#### XXX = ?
* `(a)` `0x00F000F000F00080`
* `(b)` `0xF000F000F000F000`
* `(c)` `0x0F0F0F0F0F0F0F0F`
* `(d)` `0xF0F0F0F0F0F0F0F0`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`

### 解題思路
* 從第 6 行可以看出 `((__uint128_t) M * n) >> 64` 是 `n / D` 的商 (`quotient`)
* 從上述的程式可以推導出:

$$
M \times n = quotient \times 2^{64} = \frac{n}{D} \times 2^{64}\\
\Rightarrow M = \frac{2^{64}}{D}
$$

* 但是 `uint64_t` 的上限只到 $2^{64} - 1$, 因此代入 $XXX = 2^{64} - 1$ 後再加 $1$
* 可得到 $M = \lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1$

#### 驗證 $M = \lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1$ 的正確性
* 已知:
$$
quotient = \lfloor{\frac{n}{D}}\rfloor
$$

* 且假設:
$$
2^{64} - 1 = aD + r; \text{    where 0} \leq \text{    r < D}
$$

* 證明下列式子成立:
$$
\lfloor{\frac{n}{D}}\rfloor 
= \lfloor{\frac{(\lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1) \times n}{2^{64}}}\rfloor
$$

* 推導過程:
$$
\lfloor{\frac{(\lfloor{\frac{2^{64} - 1}{D}}\rfloor + 1) \times n}{2^{64}}}\rfloor 
= \lfloor{\frac{(a + 1) \times n}{2^{64}}}\rfloor 
= \lfloor{\frac{\frac{(a + 1) \times D}{D} \times n}{2^{64}}}\rfloor
= \lfloor{\frac{\frac{(a + 1) \times D}{D} \times n}{aD + r + 1}}\rfloor 
= \lfloor{\frac{\frac{aD + D}{D} \times n}{aD + r + 1}}\rfloor 
$$

    因為 $(aD + D) \  mod \  D = 0$, 所以可以將除數 $D$ 移到被除數 $n$ 底下:
$$
\lfloor{\frac{\frac{aD + D}{D} \times n}{aD + r + 1}}\rfloor 
= \lfloor{\frac{aD + D}{aD + r + 1}}\rfloor \times \lfloor{\frac{n}{D}}\rfloor
$$

    由於 $r + 1 \leq D$，因此:
$$
\frac{aD + D}{aD + r + 1} \geq 1
\Rightarrow \lfloor{\frac{aD + D}{aD + r + 1}}\rfloor = 1
$$

    將上面結果代回推導式中:
$$
\lfloor{\frac{aD + D}{aD + r + 1}}\rfloor \times \lfloor{\frac{n}{D}}\rfloor 
= 1 \times \lfloor{\frac{n}{D}}\rfloor 
= \lfloor{\frac{n}{D}}\rfloor
= quotient
$$

* 證明完成!

:::success
Answer: `(f)` `0xFFFFFFFFFFFFFFFF`
:::

## Problem 4
### Required Functions
* 判斷是否能被整除

### Code Snippets
* `divisible`
```c=
bool divisible(uint32_t n)
{
    return n * M <= YYY;
}
```

#### YYY = ?
* `(a)` `M + 1`
* `(b)` `M`
* `(c)` `M - 1`
* `(d)` `(M >> 1)`
* `(e)` `(M << 1)`

### 解題思路
* 延續上一題，已知 $M = \frac{0xFF...F}{3} + 1$，算出 $M = 0x5555\ 5555\ 5555\ 5555 + 1$
* 已知 $D = 3$，因此考慮 $n = 3k，3k + 1，3k + 2$ 三種情況
* $n = 3k:$
$M \times n = (0x555...5 + 1) \times 3k = (0xFFF...F + 3) \times k = 0x000...02 \times k = 2k$
* $n = 3k + 1:$
$M \times n = (0x555...5 + 1) \times (3k + 1) = (0x555...5 + 1) \times 3k + (0x555...5 + 1) = 2k + M$
* $n = 3k + 2:$
$M \times n = (0x555...5 + 1) \times (3k + 2) = (0x555...5 + 1) \times 3k + (0x555...5 + 1) \times 2 = 2k + 2M$

從上面結果可發現，只要 $n \times M < M$ 就代表 $n$ 可以被 $D$ 整除，因此可能的選項有 YYY = `M - 1` 或 `(M >> 1)`。如果考慮極端值 $n = 0xFFFF\ FFFF$，則 $k\_max = 0x5555\ 5555$
結果...還是沒有辦法剔除其中一個選項

:::success
Answer: `(c)` `M - 1` or `(d)` `(M >> 1)` (maybe)
:::

## Problem 5
### Required Functions
* 將指定的字串 (或部分字串) 的英文字母全改為小寫

### Code Snippets
* `strlower` (process one `char` in each iteration)
```c=
#include <ctype.h>
#include <stddef.h>
/* in-place implementation for converting all characters into lowercase. */
void strlower(char *s, size_t n)
{
    for (size_t j = 0; j < n; j++) {
        if (s[j] >= 'A' && s[j] <= 'Z')
            s[j] ^= 1 << 5;
        else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
            s[j] = tolower(s[j]);
    }
}
```

* `strlower_vector` (process 8 chars at once)
```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(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);
}
```

#### VV1 = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`

#### VV2 = ?
* `(a)` `(-1)`
* `(b)` `0`
* `(c)` `1`

#### VV3 = ?
* `(a)` `(-1)`
* `(b)` `0`
* `(c)` `1`

#### VV4 = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`

### 解題思路
* `strlower_vector` 中的 `PACKED_BYTE(b)` 可以在 64 個 bit 中萃取出最小的 8 個 bit，然後將這 8 個 bit 複製到整個 64 bit
* 例如: `PACKED_BYTE(0x80)` => `0x8080 8080 8080 8080`

#### VV1
* VV1 沿用 [Problem 1](#Problem-1) 的技巧來判斷字串裡的字元是否都在 ASCII 表裡面，因此答案選擇 `0x80`

#### VV2, VV3
* 從 `strlower_vector` 的第 14, 15 行中，我們可以推斷它在判斷字串是否在 `'A'` 至 `'Z'` 的範圍裡
* `A`: 只要 `*chunk` 中的 字元都在 `'A'` 之後，那麼 `*chunk + PACKED_BYTE(128 - 'A' + VV2)` 的 8 的倍數的位元都會是 `1`
* `Z`: 只要 `*chunk` 中的 字元都在 `'Z'` 之前，那麼 `*chunk + PACKED_BYTE(128 - 'Z' + VV3)` 的 8 的倍數的位元都會是 `0`


| char  |  binary   | `128 - 'A' + VV2` | `128 - 'Z' + VV3` | MSB_1 ^ MSB_2 |
|:-----:|:---------:|:-----------------:|:-----------------:|:-------------:|
| `' '` | 0010 0000 |   ==0==101 1111   |   ==0==100 0101   |       0       |
| `'A'` | 0100 0001 |   ==1==000 0000   |   ==0==110 0110   |       1       |
| `'Z'` | 0101 1010 |   ==1==001 1001   |   ==0==111 1111   |       1       |
| `'a'` | 0110 0001 |   ==1==010 0000   |   ==1==000 0110   |       0       |

* 為了達到上述結果，VV2 必須是 `0`，VV3 則必須是 `(-1)`

#### VV4
* 由於我們只需要 MSB (每 8 個 bit 取一個 MSB) 來判斷是否在範圍內，因此使用 `& 0x80` 來過濾掉非必要的資訊

:::success
Answer:
VV1 = `0x80`
VV2 = 0
VV3 = (-1)
VV4 = `0x80`
:::

## Problem 6
### Required Functions
* 找到只出現過一次的值

### Code Snippets
* `singleNumber`
```c=
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;
} 
```

#### KKK = ?
* `(a)` `higher`
* `(b)` `lower`
* `(c)` `~higher`
* `(d)` `~lower`
* `(e)` `0xFFFFFFFF`

#### JJJ = ?
* `(a)` `higher`
* `(b)` `lower`
* `(c)` `~higher`
* `(d)` `~lower`
* `(e)` `0xFFFFFFFF`

### 解題思維
我們需要 2 個變數 `higher` 和 `lower` 來表示 3 個狀態，分別是 `00`，`01`，`10`，並且根據當前的 `higher`，`lower` 和 `input` 的值來決定下一個 `higher` 和 `lower` 的值
* 以下的 `input` 只有一個 bit 的長度，但此概念也可套用在多個 bit 的情況

#### Transition
* $input\_bit = 1:$ `00` => `01` => `10` => `00` => ...
* $input\_bit = 0:$ 不改變狀態
* Transition table (overall):

| higher state | lower state | input bit | (higher state)' | (lower state)' |
|:------------:|:-----------:|:---------:|:---------------:|:--------------:|
|      0       |      0      |     1     |      ==0==      |     ==1==      |
|      0       |      1      |     1     |      ==1==      |     ==0==      |
|      1       |      0      |     1     |      ==0==      |     ==0==      |
|      0       |      0      |     0     |        0        |       0        |
|      0       |      1      |     0     |        0        |       1        |
|      1       |      0      |     0     |        1        |       0        |

#### `lower` transition:
* Transition table (`lower`):

| higher state | lower state | input bit | (lower state)' |
|:------------:|:-----------:|:---------:|:--------------:|
|      0       |      0      |     1     |     ==1==      |
|      0       |      1      |     1     |     ==0==      |
|      1       |      0      |     1     |     ==0==      |
|      0       |      0      |     0     |       0        |
|      0       |      1      |     0     |       1        |
|      1       |      0      |     0     |       0        |

* 如果 $input\_bit = 0$，`lower` 不做改變，如果 $input\_bit = 1$, `lower` 狀態會變化 (`0` => `1`; `1` => `0`)，所以我們可以使用 $lower' = input\_bit \hat{} lower$ 來達到我們想要的變化
* 但是可以發現，當 $higher = 1$ 且 $input\_bit = 1$ 的時候， $lower'$ 會等於 `1`，並非我們所期望的 `0`。因此，我們也把 `higher` 加入考量
* 經過觀察，只有在 $higher = 1$ 的時候需要將 $input\_bit \hat{} lower$ 的值反轉 (`1` => `0`)，所以我們選擇先反轉 `higher`，將其變成 `0` 之後再跟 $input\_bit \hat{} lower$ 進行 bitwise AND 運算
* 最終，我們得到:
$lower' = (input\_bit \hat{} lower) \& (\text{~} higher)$
* `input` 為多個 bit 時仍適用上方公式，因此可得:
$\Rightarrow lower' = (input \hat{} lower) \& (\text{~} higher)$

#### `higher` transition:
* Transition table (`higher`):

| higher state | (lower state)' | input bit | (higher state)' |
|:------------:|:--------------:|:---------:|:---------------:|
|      0       |     ==1==      |     1     |      ==0==      |
|      0       |     ==0==      |     1     |      ==1==      |
|      1       |     ==0==      |     1     |      ==0==      |
|      0       |       0        |     0     |        0        |
|      0       |       1        |     0     |        0        |
|      1       |       0        |     0     |        1        |


* 如果 $input\_bit = 0$，`higher` 不做改變，如果 $input\_bit = 1$, `higher` 狀態會變化 (`0` => `1`; `1` => `0`)，所以我們可以使用 $higher' = input\_bit \hat{} higher$ 來達到我們想要的變化
* 但是可以發現，當 $lower' = 1$ 且 $input\_bit = 1$ 的時候， $higher'$ 會等於 `0`，並非我們所期望的 `1`。因此，我們也把 `lower'` 加入考量
* 經過觀察，只有在 $lower' = 1$ 的時候需要將 $input\_bit \hat{} higher$ 的值反轉 (`0` => `1`)，所以我們選擇先反轉 `lower'`，將其變成 `0` 之後再跟 $input\_bit \hat{} higher$ 進行 bitwise AND 運算
* 最終，我們得到:
$higher' = (input\_bit \hat{} higher) \& (\text{~} lower)$
* `input` 為多個 bit 時仍適用上方公式，因此可得:
$\Rightarrow higher' = (input \hat{} higher) \& (\text{~} lower)$

:::warning
:warning: `lower` 已在 **lower transition** 中被更新過了，因此 $higher' = (input \hat{} higher) \& (\text{~} lower)$ 中的 `lower` 即代表 `(lower state)'`
:::

:::success
Answer:
KKK = `~higher`
JJJ = `~lower`
:::

<!-- ## References -->

