# 2018q3 Homework3 (review)
Contributed by <`aben20807`>
###### tags: `sysprog2018`
<style>
.red {
color: red;
}
</style>
## 1. 第 1 週 測驗 `2`
```c=
#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;
}
```
### Question
+ N = ?
### Answer
#### 答案
此題答案是 ==N = 2==
在課堂中我是用猜的，猜測思路是一開始就選出答案只可能是 2、4、8，觀察迴圈後發現只有 2 能夠使迴圈執行大於一次，所以就猜 2。不過這只是猜測。
#### 分析
+ 建表：4\*4\*4\*4 = 256 for 8-bit (2^8^)
```c
#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)
```
+ 而 1 ^ 1 = 0, 0 ^ 1 = 1
+ 規律：0, 1, 1, 0，與 XOR 的真假值表相符合
+ 迴圈
+ 把左方的 16 bits 和右方的 16 bits 做 XOR 間接用右方 16 bits 記錄
+ 因為 XOR 的特性就是奇數個 1 才會為 1
|A|B|⊕|
|:-:|:-:|:-:|
|0|0|0|
|0|1|1|
|1|0|1|
|1|1|0|
+ 利用迴圈把 32 bits 的奇偶資訊存到 8 bits 中，再去查表得
+ 
+ [==Bit Twiddling Hacks==](https://graphics.stanford.edu/~seander/bithacks.html#ParityNaive)：題目都在這裡 OAO
+ 原始用法：
```c
static const bool ParityTable256[256] =
{
# 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)
P6(0), P6(1), P6(1), P6(0)
};
unsigned char b; // byte value to compute the parity of
bool parity = ParityTable256[b];
// OR, for 32-bit words:
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
bool parity = ParityTable256[v & 0xff];
// Variation:
unsigned char *p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];
```
+ Computing parity the naive way
+ 每次 -1 會把最右的 1 換成 0，最右的 1 右方的所有 0 變成 1
+ 所以每次 and (`&`) 都可以確定一個 `1`
+ 缺點：迴圈次數不定，用查表法可以保證常數時間
```c
unsigned int v = 1742346774;
int parity = 0;
while (v)
{
parity = !parity;
v = v & (v - 1);
}
printf("%s parity\n", parity ? "odd" : "even");
```
+ 過程：
```
01100111110110100001101000010110
01100111110110100001101000010100
01100111110110100001101000010000
01100111110110100001101000000000
01100111110110100001100000000000
01100111110110100001000000000000
01100111110110100000000000000000
01100111110110000000000000000000
01100111110100000000000000000000
01100111110000000000000000000000
01100111100000000000000000000000
01100111000000000000000000000000
01100110000000000000000000000000
01100100000000000000000000000000
01100000000000000000000000000000
01000000000000000000000000000000
even parity
```
+ 補充：(如何把一個數的二進位印出來) [[Source]](https://stackoverflow.com/a/3974138)
```c
void print_bits(size_t const size, void const *const ptr)
{
unsigned char *b = (unsigned char*) ptr;
for (int i = size - 1; i >= 0; i--){
for (int j = 7; j >= 0; j--){
printf("%u", (b[i] >> j) & 1);
}
}
puts("");
}
```
### 延伸：[CRC (Cyclic redundancy check)](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97)
+ 生成的數字在傳輸或者儲存之前計算出來並且附加到資料後面
+ 使用 XOR 來代替減法
+ 原始字串(被除數)：$M(x)$, key(除數)：$K(x)$, 校驗和(餘數)：$R(x)$
+ $M(x) \times x^n = Q(x) \times K(x) - R(x)$
+ codeword：$M(x) \times x^n + R(x)$
+ 接收者收到 codeword 後去除以 $K(x)$ 就可以知道是否正確
+ 參考[這裡](https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks#Example)的例子寫出易懂版本
+ $K(x) = x^8 + x^2 + x + 1$
```c
unsigned char get_crc(unsigned char c)
{
unsigned int mask = (1 << 15);
unsigned int poly = (0b100000111 << 7);
unsigned int crc = (c << 8);
for (int j = 0; j < 8; j++) {
if (crc & mask) {
crc ^= poly;
}
mask >>= 1;
poly >>= 1;
}
return crc;
}
int main()
{
unsigned char c = 'W'; // 01010111
unsigned char crc = get_crc(c); // 10100010
return 0;
}
```
+ 去掉 mask
```c
unsigned char get_crc(unsigned char c)
{
unsigned int poly = (0b100000111 << 7);
unsigned int crc = (c << 8);
for (int i = 0; i < 8; i++) {
if ((crc >> (16 - i - 1)) & 1) {
crc ^= poly;
}
poly >>= 1;
}
return crc;
}
```
+ 發現 linux 內部也有 crc 系列的函式，裡面有提到相關演算法的參考：[A Painless Guide to CRC Error Detection Algorithms](http://www.ross.net/crc/download/crc_v3.txt)
+ 稍微改造一下 [torvalds/linux/lib/crc8.c](https://github.com/torvalds/linux/blob/master/lib/crc8.c)
```c
#include <stdint.h>
#define CRC8_TABLE_SIZE 256
typedef uint8_t u8;
typedef uint16_t u16;
void crc8_populate_msb(u8 table[CRC8_TABLE_SIZE], u16 polynomial)
{
int i, j;
const u8 msbit = 0x80;
u8 t = msbit;
table[0] = 0;
for (i = 1; i < CRC8_TABLE_SIZE; i *= 2) {
t = (t << 1) ^ (t & msbit ? polynomial : 0);
for (j = 0; j < i; j++)
table[i+j] = table[j] ^ t;
}
}
u8 crc8(const u8 table[CRC8_TABLE_SIZE], u8 pdata, u8 crc)
{
crc = table[(crc ^ pdata++) & 0xff];
return crc;
}
int main ()
{
unsigned char c = 'W';
unsigned char table[CRC8_TABLE_SIZE];
crc8_populate_msb(table, 0b100000111); // 這裡 K(x) 為 9 bits 所以改用 u16
unsigned char crc = crc8(table, c, 0); // 10100010 結果相同!
return 0;
}
```
+ 印出 table
```c
unsigned char table[CRC8_TABLE_SIZE];
crc8_populate_msb(table, 0b100000111);
for (int i = 0; i < CRC8_TABLE_SIZE; i++) {
printf("%4d", table[i]);
if ((i + 1) % 16 == 0)
puts("");
}
```
```
0 7 14 9 28 27 18 21 56 63 54 49 36 35 42 45
112 119 126 121 108 107 98 101 72 79 70 65 84 83 90 93
224 231 238 233 252 251 242 245 216 223 214 209 196 195 202 205
144 151 158 153 140 139 130 133 168 175 166 161 180 179 186 189
199 192 201 206 219 220 213 210 255 248 241 246 227 228 237 234
183 176 185 190 171 172 165 162 143 136 129 134 147 148 157 154
39 32 41 46 59 60 53 50 31 24 17 22 3 4 13 10
87 80 89 94 75 76 69 66 111 104 97 102 115 116 125 122
137 142 135 128 149 146 155 156 177 182 191 184 173 170 163 164
249 254 247 240 229 226 235 236 193 198 207 200 221 218 211 212
105 110 103 96 117 114 123 124 81 86 95 88 77 74 67 68
25 30 23 16 5 2 11 12 33 38 47 40 61 58 51 52
78 73 64 71 82 85 92 91 118 113 120 127 106 109 100 99
62 57 48 55 34 37 44 43 6 1 8 15 26 29 20 19
174 169 160 167 178 181 188 187 150 145 152 159 138 141 132 131
222 217 208 215 194 197 204 203 230 225 232 239 250 253 244 243
```
:::warning
## 不懂之處
+ 兩個奇怪的部份：
1. CRC 中的 $K(x)$ 也就是除數 (polynomial) 的最高次方大多與資料的位元數相同
+ e.g. CRC-8-ATM: $x^8 + x^2 + x + 1$ ( `100000111`)
這樣用意可能是確保 CRC (餘數) 有 8 bits，不過 $K(x)$ 就需要用 9 bits。若在 64 bits 的情況下代表需要 65 bits，這不是用 16 bits 存 9 bits 就可以解決的。
2. [linux](https://github.com/torvalds/linux/tree/master/lib) 中 crc4 ~ 64 的實作差異相當大，無法理解。
:::
## 2. 第 2 週 測驗 `3`
### Question
+ Linux 核心程式碼 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L463h) 提到以下程式碼，為何每個 head 使用時都要先加上 `()` 呢？
```c
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
```
### Answer
+ 因為==運算子的優先順序 (Operator Precedence)==
+ `->` 的優先度很高，尤其是比 `*` (dereference) 還要優先
+ 因此 `*head->prev` 等價於 `*(head->prev)` 並不符合程式需求
+ 由於 macro 是展開程式碼，例如以下程式碼在**編譯時期**就會產生錯誤
```c
#include <stdio.h>
typedef struct _A { int data; } A;
#define pdata(x) \
printf("%d\n", x->data);
int main() {
A a = { .data = 123 };
pdata(&a);
return 0;
}
```
```
q3.c: In function ‘main’:
q3.c:5:21: error: invalid type argument of ‘->’ (have ‘A {aka struct _A}’)
printf("%d\n", x->data);
^
q3.c:9:5: note: in expansion of macro ‘pdata’
pdata(&a);
^~~~~
```
+ macro 必須改成
```c
#define pdata(x) \
printf("%d\n", (x)->data);
```
### 延伸
+ [https://www.mcs.anl.gov/~kazutomo/list/list.h](https://www.mcs.anl.gov/~kazutomo/list/list.h)
+ [`#define __labelset_for_each(LS, N) \`](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/security/apparmor/include/label.h#L81)
## 3. 第 2 週 測驗 `4`
### Question
```c
int B = 2;
void func(int *p) { p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
### Answer
```c
int B = 2;
void func(int **p) { *p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(&ptrA);
printf("%d\n", *ptrA);
return 0;
}
```
+ 傳入函式的參數都是**副本**
+ 在 `main()` 中 `ptrA` 指向 `A`
+ 若要在 `func()` 中改變 `ptrA` 所指向的內容就必須傳入 pointer to pointer，也就是 `&ptrA` (address of ptrA) 這樣在 `func()` 中才能透過 `*(&ptrA)` (dereference) 來修改指向 `ptrA` 的值變成指向 `B`
+ 否則原本的 `func()` 中的 `p` 的生命周期只限於 `func()` 內
### 延伸
連結：[git/progress.c `void stop_progress_msg(struct progress **p_progress, const char *msg)`](https://github.com/git/git/blob/master/progress.c#L232-L260)
+ 要把傳入的指標 free 後設成 `NULL`, 若只傳入 pointer 則不會改變到外部的值
+ 簡化與添加測試如下：
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct _A { int data; } A;
typedef struct _B { A *a; } B;
void freeb_wrong(B *b)
{
free(b->a);
free(b);
b = NULL;
}
void freeb(B **p_b)
{
B *b = *p_b; // 此為參照上方連結中的寫法
*p_b = NULL;
free(b->a);
free(b);
}
int main()
{
B *b1 = malloc(sizeof(B));
b1->a = malloc(sizeof(A));
printf("%p\n", b1); // 0x563ed8400260
freeb_wrong(b1);
printf("%p\n\n", b1); // 0x563ed8400260
B *b2 = malloc(sizeof(B));
b2->a = malloc(sizeof(A));
printf("%p\n", b2); // 0x563ed8400260
freeb(&b2);
printf("%p\n", b2); // (nil)
return 0;
}
```
## 4. 第 3 週 測驗 `2`
### Question
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```c
int main() {
union {
int a;
char b;
} c = { .a = K1 };
return c.b == K2;
}
```
### Answer
==K1 = 1, K2 = 1==
+ int : 4bytes, char: 1byte
+ 若為 little-endian 則 `0x01` 會放在最低的位址
```
higher memory
----->
+----+----+----+----+
|0x01|0x00|0x00|0x00|
+----+----+----+----+
|char|
|<------ int ------>|
```
### 其他種方式
#### 1. 同樣利用 int 和 char，但是是用 cast 的方式 [[source]](https://www.geeksforgeeks.org/little-and-big-endian-mystery/)
```c
bool is_le2()
{
int x = 1;
char *y = (char*)&x;
return *y;
}
```
```
higher memory
----->
little:
+----+----+----+----+
|0x01|0x00|0x00|0x00|
+----+----+----+----+
^
|
&x
big:
+----+----+----+----+
|0x00|0x00|0x00|0x01|
+----+----+----+----+
^
|
&x
```
#### 2. 利用 cast，把兩個 char cast 成一個 short [[source]](https://www.geeksforgeeks.org/little-and-big-endian-mystery/)
```c
bool is_le3()
{
char arr[2] = {0x01, 0x00};
short x = *(short *)arr;
return x == 1;
}
```
#### 3. 改良原本版本 [[source]](https://stackoverflow.com/a/2100549)
```c
bool is_le4()
{
return !!((union {
int a;
char b;
}){ .a = 1 }.b);
}
```
## 5. 第 3 週 測驗 `3`
### Question
以下程式碼計算 parity bit:
```c
#include <stdint.h>
int parity(uint32_t x)
{
x ^= x >> 1;
x ^= x >> 2;
x = (x & 0x11111111U) * 0x11111111U;
return (x >> P) & 1;
}
```
### Answer
==P = 28==
### 分析
#### 最笨的方法：printf 大法
```c
int parity_steps(uint32_t x)
{
printf("x\t\t"); print_bits(sizeof(x), &x);
uint32_t y = x >> 1;
printf("x >> 1\t\t"); print_bits(sizeof(y), &y);
x ^= y;
printf("x ^= x >> 1\t"); print_bits(sizeof(x), &x);
y = x >> 2;
printf("x >> 2\t\t"); print_bits(sizeof(y), &y);
x ^= y;
printf("x ^= x >> 2\t"); print_bits(sizeof(x), &x);
y = x & 0x11111111U;
printf("x & @\t\t"); print_bits(sizeof(y), &y);
y *= 0x11111111U;
printf("(x & @) * @\t"); print_bits(sizeof(y), &y);
y >>= 28;
printf("x >>= 28\t"); print_bits(sizeof(y), &y);
x = y & 1;
printf("x & 1\t\t"); print_bits(sizeof(x), &x);
return x;
}
```
```
x 01100111110110100001101000010110
x >> 1 00110011111011010000110100001011
x ^= x >> 1 01010100001101110001011100011101
x >> 2 00010101000011011100010111000111
x ^= x >> 2 01000001001110101101001011011010
x & @ 00000001000100000001000000010000
(x & @) * @ 01000100001100100010000100010000
x >>= 28 00000000000000000000000000000100
x & 1 00000000000000000000000000000000
```
#### 開始有點頭緒：
1. `x ^= x >> 1`：把奇偶資訊存在偶數 bit 中
2. `x ^= x >> 2`：把奇偶資訊存在被 4 整除的 bit 中
3. 和 `0x11111111U (0b00010001000100010001000100010001)` 做 Bitwise AND 相當於清空被 4 整除以外的 bit
4. 再和 `0x11111111U` 相乘，會把每個被 4 整除的 bit 累加在第 29 bit，因此若有奇數個最後第 29 bit 就為 `1`，否則為 `0`
5. 右移 28 bit 再和 `1` 做 Bitwise AND 就可得答案
<pre>
+-+-+-+-+-+-+-+-+
|1|0|0|1|1|1|0|1| ---┐
+-+-+-+-+-+-+-+-+ | 1. x ^= x >> 1
+-+-+-+-+-+-+-+-+ | 把資訊存在偶數 bit
|1|<span class="red">1</span>|0|<span class="red">1</span>|0|<span class="red">0</span>|1|<span class="red">1</span>| <--┘
+-+-+-+-+-+-+-+-+ | 2. x ^= x >> 2
+-+-+-+-+-+-+-+-+ | 把資訊存在被 4 整除的 bit
|1|1|1|<span class="red">0</span>|0|1|1|<span class="red">1</span>| <--┘
+-+-+-+-+-+-+-+-+ | 3. x & 0x11U (0b00010001)
+-+-+-+-+-+-+-+-+ | 清空被 4 整除以外的 bit
|0|0|0|<span class="red">0</span>|0|0|0|<span class="red">1</span>| <--┘
+-+-+-+-+-+-+-+-+
4. 00000001
x)00010001
----------
00000001
00000001
------------
000<span class="red">1</span>0001
5. 00010001 >> 4 -> 00000001
00000001 & 1 -> 00000001 -> 奇數個
</pre>
### SIMD
[==Compute parity in parallel==](https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel)
```c=
unsigned int v; // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;
```
:::warning
## 不懂之處
裡面 [[link]](https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel) 說明提到在某些情況下可以刪除第 2、3 行，減少成用 5 個運算就完成。思考很久還是不懂為何能夠刪除。因此還無法參透這個寫法如何平行化。
:::
[Using SIMD on amd64, when is it better to use more instructions vs. loading from memory?](https://stackoverflow.com/a/41707900)
Sign in with Wallet
Connect another wallet