---
title:
image:
description:
tags: NCKU Class , 進階電腦系統理論與實作 , 2020q3
---

# 2020q3 Homework2 (quiz2)
contributed by < `TsenEN` >
> [題目](https://hackmd.io/@sysprog/2020-quiz2)
> [作業要求](https://reurl.cc/r85ko4)

## 測驗 1
作業介紹了 7 位碼 `ASCII` 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (`extended ASCII`)。

既然採用 `7 bits`，則必會是以下表現方式 (`1 bytes = 8bits` , 這邊以 `8 bits` 說明)

| Value |
| ----- |
|00000000|
|00000001|
|........|
|01111111|

digraph {
        rankdir=LR;
        node [shape=none];
        edge [arrowhead=vee,headclip=false, tailclip=false]
        
        MSB[shape=plaintext,fontcolor=red]
        LSB[shape=plaintext,fontcolor=blue]

        A [label=<
            <TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
            <TR>
                  <TD PORT="M">0</TD>
                  <TD PORT="">1</TD>
                  <TD PORT="">1</TD>
                  <TD PORT="">0</TD>
                  <TD PORT="">0</TD>
                  <TD PORT="">0</TD>
                  <TD PORT="">0</TD>
                  <TD PORT="L">1</TD>

              </TR>
            </TABLE>>];

        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=R; 
            MSB -> A:M;
        }
        
        {
        node [shape=record];
        edge [arrowhead=vee,headclip=true, tailclip=true]
            rank=same; 
             LSB -> A:L;
        }
}

我們可以很簡單觀察到一個特性是 `MSB` 都是 `0`，這是一個很重要的資訊！因為如果今天我們想判斷這個 1 個 `Bytes` 是不是 `ASCII 碼`，我只需要 `0X80` 來判斷！

 if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 , (0x80) = 0b10000000*/

今天 `str[i]` 去 `& 0x80` 只要 `MSB` 是 `0` ,`if` 就不會成立因為它就是 `ASCII 碼`。

所以來回答當我們要一次比對 64 位元的資料 (即 word size)， 這個 MMM 要是什麼 ?
很簡單就是 `0x8080808080808080` ，因為 `1 bytes = 8bits` 所以 `64 bits` 是 `8 Bytes`, `1 Bytes` 需要一個 `80` ，八個那就 `8080808080808080`。

### `MMM`

- [ ] `(a) 0x0080008000800080`
- [ ] `(b) 0x8000800080008000`
- [ ] `(c) 0x0808080808080808`
- [x] `(d) 0x8080808080808080`
- [ ] `(e) 0x8888888888888888`
- [ ] `(f) 0xFFFFFFFFFFFFFFFF`

### 延伸問題
待整理
* [可不可以用 casting 的方法來取得 payload 呢？](https://hackmd.io/@RinHizakura/SJ5NuIANP)
* [C 標準庫源碼解析：內存拷貝與字符串拷貝](https://blog.xiocs.com/archives/181/)
* [ARM immediate value encoding](https://alisdair.mcdiarmid.org/arm-immediate-value-encoding/)
* [Barrel Shifter](https://reurl.cc/av4aeD)

## 測驗 2
開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值

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

> 已知 `in` 一定隸屬於 '0', '1', '2', `…`, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15，且 `hexchar2val('0')` 回傳 0，其他輸入都有對應的數值。

`'0'`, `'1'`, `'2'`, `…`, `'9'` 對應到 `0x30`, `0x31`, `0x32`, `…` `0x39`
`'a'`, `'b'`, `'c'`, `…`, `'f'` `(小寫)` 對應到 `0x61`, `0x62`, `0x63`, `…`, `0x66`
`'A'`, `'B'`, `'C'`, `…`, `'F'` 對應到 `0x41`, `0x42`, `0x43`, `…`, `0x46`

先列出 `in` Domain 裡的數值來找特性

| 字元 | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 |
| ----- | --- | ----- | --- | --- | --- | --- |:--- |:--- |
| `'0'` | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| `'9'` | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| `'a'` | 0 | ==1== | 1 | 0 | 0 | 0 | 0 | 1 |
| `'f'` | 0 | ==1== | 1 | 0 | 0 | 1 | 1 | 0 |
| `'A'` | 0 | ==1== | 0 | 0 | 0 | 0 | 0 | 1 |
| `'F'` | 0 | ==1== | 0 | 0 | 0 | 1 | 1 | 0 |

`0~9` 就直接是要轉換的數值，再去觀察 `return (in + shift) & 0xf;` ，`& 0xf` 代表 `b3~b0` 會 `return` 回去，這意味著 `shift` 要是 `0b00000000` 。

`a~f` 、 `A~F` 只有 `b6` 會是一樣並且 `0~9` 的 `b6 = 0`，所以可以看到 `letter` 是用來區分英文與數字的，那這樣就很明確 `b6` 會是關鍵，因為它可以區分兩者，故選 `(c)`。
### `MASK`

- [ ] `(a) 0x10`
- [ ] `(b) 0x20`
- [x] `(c) 0x40`
- [ ] `(d) 0x60`
- [ ] `(e) 0x80`

再來我們觀察 `a~f` 、 `A~F` 的 `b3~b0` 數值區間是 `1~6` 而不管大小寫 `a~f` 是 `10~15` ，這代表我們要加 `9` ，所以我們可以利用 `letter` 配出來，因為 `letter` 是 `2^6^` 所以我們 right shift `3 bits`(等於除以 `2^3^`)得到`8 = 0b00001000` 再 right shift `6 bits`(等於除以 `2^6^`)得到`1 = 0b00000001` 再 `or` 就可以得到 `9 = 0b00001001`。

### `AAA`

- [x] `(a) 3`
- [ ] `(b) 2`
- [ ] `(c) 1`
- [ ] `(d) 0`

### `BBB`

- [ ] `(a) 7`
- [x] `(b) 6`
- [ ] `(c) 5`
- [ ] `(d) 4`

## 測驗 3
建議可以先看延伸問題的 [src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 的註解

### Magic number M
Suppose $n = q·d$ for some integer $q$, we have

\begin{align}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}
\newcommand{\naturals}[]{\mathbb{N}}
&\floor{\ceil{\frac{2^k}{d}} \cdot \frac{n}{2^k}} \\
=& \floor{\frac{2^k+r}{d} \cdot \frac{n}{2^k}} \\
=& \floor{\ ( \frac{2^k}{d}\ + \frac{r}{d}\ ) \cdot \frac{n}{2^k}} \\
=& \floor{\frac{n}{d}\ + \frac{r}{d} \cdot \frac{n}{2^k} } \\
=& \frac{n}{d}\ +\ \floor{\frac{r}{d} \cdot \frac{n}{2^k} } \\
\end{align}

where $2^k+r = q'·d$ for some integer $r,q'$ and $r<d$. Because $r = -(2^k) mod$ $d$ ,so $\frac{r}{d} <1$, if we select $k$ such that $\frac{n}{2^k} < 1$, we'll have $\frac{r}{d} \cdot \frac{n}{2^k} < 1$ and

\begin{align}
&\frac{n}{d}\ +\ \floor{\frac{r'}{d} \cdot \frac{n}{2^k} } = \frac{n}{d}\
\end{align}

上面這段數學推導給出了一個很棒的想法，**只要今天 n 是被 d 整除且我們選擇的 k 夠大**我們就可以用 $\ceil{\frac{2^k}{d}}$ 當作 magic number $M$。**要做除法時就做 $n \cdot M \cdot \frac{1}{2^k}$ 即可**，對應到 c 語言中，即是乘法與位移兩個動作。

### Back the test 3
並且我們可以應用上面證明的方式來回答測驗 3 ， 先來看看數學推導。

Suppose $n = qd + r$ for some $q$ , $0\le r<d$ . Then, we have
\begin{align}
&\floor{\ceil{\frac{2^N}{d}} \cdot n \cdot \frac{1}{2^N}} \\
=& \floor{\frac{2^N+r'}{d} \cdot n \cdot \frac{1}{2^N}} \\
=& \floor{\frac{n}{d}\ +\ \frac{r'}{d} \cdot \frac{n}{2^N} } \\
=& \floor{q + \frac{r}{d}\ +\ \frac{r'}{d} \cdot \frac{n}{2^N} } \\
=&\ q\ +\ \floor{\frac{r}{d}+\frac{r'}{d} \cdot \frac{n}{2^N} }.
\end{align}

$r' = -(2^k) mod$ $d$

The first and second equality comes from the same reasoning in the jemalloc case. The third equality comes from the fact that $\frac{n}{d} = q+\frac{r}{d}$. The final equality stands because $q$ is an integer.
The final line equals to $q$ only if **$\frac{r}{d}+\frac{r'}{d} \cdot \frac{n}{2^N} < 1$** 得到這個重要資訊，先停下來。

先來推理程式給我們的資訊。

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

預期 `quickmod(5)` 會得到 `2` , `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (555 是 3 的倍數)。

看得出來是要取餘數 ! `return n - quotient * D` 透過剛剛提示看得出來是要回傳餘數，我們可以思考一下得出，$n$ $mod$ $d$ $= n − (n/d)×d$，所以`quotient`就是 $(n/d)$ 。

而 $(n/d)$ 這個除法看了很討厭，所以我們就要把他轉成乘法與位移的處理 $\dfrac{n}{d}=n\times\dfrac{\dfrac{2^N}{d}}{2^N}$ ，看到 `>> 64` 不難看出是除以 2^64^ 所以 `N = 64`，但對應的$M卻不等於 \dfrac{2^N}{d}$ 而是 $M=\dfrac{2^N-1}{d} + 1$ (這是因為答案只有 `0xFFFFFFFFFFFFFFFF` $=2^{64}-1$ ) 因此要證明兩者最終結果是相等的。

### 推導 `0xFFFFFFFFFFFFFFFF` 是否符合等式

$\ceil{\dfrac{2^N}{d}} = \floor{\dfrac{2^N-1}{d}} + 1, ( 2^N,d > 0 ) , 令 2^N = q·d + r ,0\le r<d.$

Here we need to consider two case

$r = 0$
\begin{align}
&\ceil{\frac{2^N}{d}} \\
=&\ceil{\frac{q·d}{d}}\\
=& q
\end{align}

---

\begin{align}
&\floor{\frac{2^N-1}{d}}+1 \\
=&\floor{\frac{2^N-1}{d}+1} \\
=&\floor{\frac{q·d-1}{d}+1} \\
=&\floor{\frac{q·d-1+d}{d}} \\
=&\floor{\frac{(q+1)d-1}{d}} \\
=&\floor{\frac{(q+1)d}{d}\ - \frac{1}{d}} \\
=&\floor{q+( 1\ - \frac{1}{d})} \\
=& q
\end{align}

$r > 0$
\begin{align}
&\ceil{\frac{2^N}{d}} \\
=&\ceil{\frac{q·d+r}{d}}\\
=&\ceil{\frac{q·d+r}{d}}\\
=&q+\ceil{\frac{r}{d}}\\
=&q+1
\end{align}

---

\begin{align}
&\floor{\frac{2^N-1}{d}}+1 \\
=&\floor{\frac{2^N-1}{d}+1} \\
=&\floor{\frac{q·d+r-1}{d}+1} \\
=&\floor{\frac{q·d+r-1+d}{d}} \\
=&\floor{\frac{(q+1)d+r-1}{d}} \\
=&\floor{\frac{(q+1)d}{d}\ + \frac{r-1}{d}} \\
=&\floor{q+1\ - \frac{r-1}{d}} \\
\end{align}

因為 $1\le r<d$，所以 $0 \le \frac{r-1}{d}<1$，這樣就得到
\begin{align}
&\floor{q+1\ - \frac{r-1}{d}} \\
=&\floor{q+1} \\
=&q+1 \\
\end{align}

由上述得證對於數學推導有疑問可看這篇 [C++中 整數除法 向上取整的數學證明](https://reurl.cc/A84yge)，數學符號 [LATEX 語法筆記](https://reurl.cc/odrZ9j)

好所以很棒我們整合前面的一堆推導
\begin{align}
&\floor{\ceil{\frac{2^N}{d}} \cdot n \cdot \frac{1}{2^N}} \\
=&\floor{ \floor{\dfrac{2^N-1}{d}} + 1 \cdot n \cdot \frac{1}{2^N}} \\
=&\ q\ +\ \floor{\frac{r}{d}+\frac{r'}{d} \cdot \frac{n}{2^N} } \\
\end{align}

我們需要回去討論 **$\frac{r}{d}+\frac{r'}{d} \cdot \frac{n}{2^N} < 1$**，已知 $r,r' < d ,因為都是 mod$ $d$，而因為`uint32_t n` 所以 $n$ 被限制最大表示只能到 $2^{32} -1$ 又 $N = 64$ 可以得到 $\frac{n}{2^N} < 1$，$\frac{n}{d} = q+\frac{r}{d}$ ($\frac{r}{d}$ 會被程式捨掉)所以 $\frac{n}{d} = q$ 恭喜我們可以選答案了 !

### `XXX`

- [ ] `(a) 0x00F000F000F00080`
- [ ] `(b) 0xF000F000F000F000`
- [ ] `(c) 0x0F0F0F0F0F0F0F0F`
- [ ] `(d) 0xF0F0F0F0F0F0F0F0`
- [ ] `(e) 0x8888888888888888`
- [x] `(f) 0xFFFFFFFFFFFFFFFF`

## 測驗 4
延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

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

以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即白痴是三的倍數)