# 2018q3 Homework3 (review)
contributed by < [`amikai`](https://github.com/amikai) >
###### tags: `sysprog2018`
# Week1 測驗2
## 題目
parity (check) bit 可翻譯為「奇偶校驗位元」或「同位檢查位元」，常見於降低資料傳輸的錯誤。在資料傳送出去前，先在資料原有位元額外加上一個 parity bit，再將 parity bit 與資料的位元所組成的位元傳送出去，待接收完畢後，就檢查看看是否有奇數個 `1` 或偶數個 `1`，以判斷有無發生錯誤。
parity bit 有兩種類型：
* 偶校驗位 (even): `1` 的個數加起來須為偶數個
* 奇校驗位 (odd): `1` 的個數加起來須為奇數個
範例 1:
* 輸入: 254
* 輸出: odd parity
* 解釋
* 254~10~ 的二進位表示為 `11111110`，其中共有 7 個 `1`，奇數個
範例 2:
* 輸入: 1742346774
* 輸出: even parity
同位元檢查已經廣泛地應用到電腦的主記憶體，其優點是只要利用 XOR 或 NOT，就能製造成硬體；缺點則是無法更正錯誤，也無法偵測到所有錯誤，一旦接收到的位元圖樣同時有偶數個 (2, 4, 6, ...個) 位元錯誤，就偵測不到錯誤，因為在這種情況下，`1` 的個數仍舊會維持奇數個或偶數個。
考慮到以下判斷 parity bit 的程式碼
```cpp
#include <stdio.h>
/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)
/* LOOK_UP is the macro expansion to generate table */
unsigned int table[256] = { LOOK_UP };
int parity(int num) {
/* Number is considered to be of 32 bits */
int max = 16;
// Dividing the number into 8-bit
// chunks while performing XOR
while (max >= 8) {
num = num ^ (num >> max);
max /= N;
}
// Masking the number with 0xff (11111111)
// to produce valid 8-bit result
return table[num & 0xff];
}
int main() {
unsigned int num = 1742346774;
/* Result is 1 for odd parity, 0 for even parity */
int result = parity(num);
printf("%s parity\n", parity(num) ? "odd" : "even");
return 0;
}
```
## 詳解
NOTE: 以下皆用 odd parity 舉例
找到 parity bit 的方法就是把數字轉成二進位的每個位數 xor, 舉例: 在四位元的情況下 7的二進位 = 0111, 則 parity bit = 0 ^ 1 ^ 1 ^ 1
我們可以先用 divide and conquer 的方式先將位數切一半並且互相 xor, 直到第一位則結束, 以下為 32 bits 的程式碼
```clike=
// 32bits parity
x ^= 16
x ^= 8
x ^= 4
x ^= 2
x ^= 1
```
如果以 4 bits 詳細來看的程式長這樣,
```clikes
x ^= 2
x ^= 1
```
ref : http://www.techiedelight.com/compute-parity-number-using-lookup-table/
以上面這個為基礎繼續發想，做出一個 32 bits 的 lookup table 代價不小, 需要花 2 的 32 次方 bits 的大小, 那我們可以取折中方案, 做一個較小的 lookup table, 可以先做一些 partiy 的運算, 算到大小小到可以查 lookup table
那簡單來說可以將程式分成兩部分:
1. 先做查找 parity 的運算, 算到足以小到可以查表
2. 查表
這其實就是這題所用到的技巧, 這題想算 32 bits 的 parity bits, 但是只有 8 bits partiy bit 的表,
所以程式的第一部份先算到足以可以查表:
```clike=
x ^= 16
x ^= 8
```
改寫之後會變成
```clike=
while (max >= 8) {
num = num ^ (num >> max);
max /= 2;
}
```
最後再查表
```clike=
table[num & 0xff];
```
再來講表是怎麼產生出來的, 這部分我先將 16 bits 的 parity bit 都列出並作觀察, 以 16bits lookup table 舉例:
從上圖可以看到 4 bits 的 table 一開始會以 2bits 的 look table 為單位做出 `v`, `v^1`, `v^1`, `v`
以此 6bits 的 lookup table 會是以 4bits的 lookup talbe 為基礎繼續做同樣的事情
而且這支程式獨特的地方就是在 compile time 就把 table 算出來啦
# Week2 測驗2
## 題目
Linux 核心程式碼 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 提到以下程式碼，為何每個 `head` 使用時都要先加上 `()` 呢？
```C
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
```
## 詳解
[以這段程式碼來看](https://elixir.bootlin.com/linux/latest/source/block/elevator.c#L376)
```clike
list_for_each_prev(entry, &q->queue_head) {
...
}
```
假設在沒有使用括號的情況下展開會變這個樣子
```clike
for (pos = &q->queue_head->prev; pos != &q->queue_head; pos = pos->prev)
```
因為 `->` 優先權大於 `&` 所以就跟以下這支程式等價
```clike
for (pos = &(q->queue_head->prev); pos != &(q->queue_head); pos = pos->prev)
```
預期的行為是這個樣子:
```clike
for (pos = (&q->queue_head)->prev; pos != &q->queue_head; pos = pos->prev)
```
所以在 macro 加上括號就會等價
# Week2 測驗7
## 題目
推敲以下程式碼的作用:
```C
void hex2(unsigned int x) {
do {
char c = "0123456789abcdef" [x & 0xf];
printf("char %c for %d\n", c, x);
x >>= 4;
printf("char %c for %d\n", c, x);
} while (x);
}
```
:::success
延伸問題: 在 [glibc](https://www.gnu.org/software/libc/) 原始程式碼找出類似作用和寫法的程式碼，並探討其實作技巧
:::
## 詳解
這段程式碼其實就是把十進位的數字(unsigned int) 轉成 16 位元的數值但是是以字元型態印出:
先將 16進制的每一位取出, 取出之後拿去查表, 此表則是一個數值相對應的 16 近制字元
以下用 176當例子:
以下是 [glibc 的例子](https://code.woboq.org/userspace/glibc/resolv/nss_dns/dns-host.c.html#499)
```clike
const u_char *uaddr = (const u_char *)addr;
case AF_INET6:
qp = qbuf;
for (n = IN6ADDRSZ - 1; n >= 0; n--)
{
static const char nibblechar[16] = "0123456789abcdef";
*qp++ = nibblechar[uaddr[n] & 0xf];
*qp++ = '.';
*qp++ = nibblechar[(uaddr[n] >> 4) & 0xf];
*qp++ = '.';
}
strcpy(qp, "ip6.arpa");
break;
```
這一小段程式其實就是想把 `uaddr` 陣列裡的 ipv6 數值轉為字元, 並且放入 `qp` 陣列, 在這邊看到最後程式加入了 `ip6.apra` 字樣, 此檔名又是 dns-host.c, 推測是 [IPv6 reverse resolution](https://en.wikipedia.org/wiki/Reverse_DNS_lookup#IPv6_reverse_resolution)
可以從 [IPv6 reverse resolution](https://en.wikipedia.org/wiki/Reverse_DNS_lookup#IPv6_reverse_resolution) 這裡的例子看見, 其實就是要做以下 line1 到 line2 的轉換
```clike=
2001:db8::567:89ab
b.a.9.8.7.6.5.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.8.b.d.0.1.0.0.2.ip6.arpa
```
uaddr 每個元素是 1 byte, 也就是 8 bits. 一個 16 進位只要存 4 bits, 所以一個 uaddr 元素可以存兩個 16 進位的數值, 所以要做兩次查表 (high 8 bits and low 8 bits):
```clike
*qp++ = nibblechar[uaddr[n] & 0xf];
*qp++ = nibblechar[(uaddr[n] >> 4) & 0xf];
```
迭代 `uaddr` 陣列是由大到小的順序, 推測是 ipv6 使用 Big-endian order
Sign in with Wallet
Connect another wallet