# 2018q3 Homework3 (review)
contributed by < `ofAlpaca` >
###### tags: `CSIE5006` `HW`
---
### 第 3 週測驗題 測驗 `1`
考慮以下程式碼:
```C=
#include <stdio.h>
#include <stdint.h>
struct test {
unsigned int x : 5;
unsigned int y : 5;
unsigned int z;
};
int main() {
struct test t;
printf("Offset of z in struct test is %ld\n",
(uintptr_t) &t.z - (uintptr_t) &t);
return 0;
}
```
在 GNU/Linux x86_64 環境中執行，得到以下輸出:
```
Offset of z in struct test is 4
```
倘若將第 10 和第 11 換為以下:
```C=10
printf("Address of t.x is %p", &t.x);
```
會發生什麼事？
==編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員;==
:::success
延伸問題: 解釋原因，並且找出 C99/C11 規格書對應的描述
:::
- [x] 根據 C99 說明可以得知， address 最小的單位是 byte ，而且無法對 bit-field 的 member 使用 `&` operator 。
> C99 [3.2] alignment
requirement that objects of a particular type be located on storage boundaries with addresses that are particular multiples of a byte address.
> C99 [6.7.2.1] The unary & (address-of) operator cannot be applied to a bit-field object; thus, there are no pointers to or arrays of bit-field objects.
- [x] 為什麼 z 和 x 的 offset 是 4 ? ([source](http://opass.logdown.com/posts/743054-about-memory-alignment))
* 最主要原因是 structure alignment 有關
* 試想以下的資料結構 :
```
strcut S {
char y; // 1 byte
int z; // 4 bytes
};
```
* 出乎意料的是 `sizeof(S)` 不會是 1 + 4 = 5 而是 8 ，這是為了 access memory 時能更加有效率， struct member 是會自動對齊的。
```
(hex)
0x0000 : yy 00 00 00
0x0004 : zz zz zz zz
--------------------
&S = 0x0000
&y = 0x0000
&z = 0x0004
```
* 由此可知 `z` 的 offset 是 &z - &S = 4 。
* 回到 `struct test` 來看，其 structure alignment 應該會是 :
```
(binary)
0x0000 : xxxx xyyy yy00 0000 0000 0000 0000 0000
0x0004 : zzzz zzzz zzzz zzzz zzzz zzzz zzzz zzzz
--------------------
&S = 0x0000
&y = 0x0000
&z = 0x0004
```
* 這就是為什麼 `z` 的 offset 為 0x0004 - 0x0000 = 4 。
---
### 第 3 週測驗題 測驗 `2`
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```C
int main() {
union { int a; char b;
} c = { .a = K1 };
return c.b == K2;
}
```
補完上述程式碼。
K1 = ?
==1==
K2 = ?
==1==
:::success
延伸問題: 解釋運作原理，並找出類似的程式碼
:::
- [x] union 的 members 會使用相同位置的記憶體，但可能因為 endian 的不同而讀到不同的 byte :
* 在 Little endian 時，因為低位元組先存在低位址，所以 char 與 int 都可讀到相同 0x01 的位元組 。
* 在 Big endian 時，因為高位元組先存在低位址，所以 char 的範圍讀不到 0x01 的那個位元組。
- [x] 類似的檢測 endianness 的程式碼 : ([source](https://www.geeksforgeeks.org/little-and-big-endian-mystery/))
```clike
#include <stdio.h>
int main()
{
unsigned int i = 1;
char *c = (char*)&i;
if (*c)
printf("Little endian");
else
printf("Big endian");
return 0;
}
```
* 原理是一樣的，在 little endian 的狀況下可以知道 0x01 的 byte 會先被放在低位址，所以轉型後 `char * c` 還讀得到 ; 相反的，如果是 big endian ， 0x01 這個 byte 會被放在高位址， `char * c` 的範圍只有 1 byte ，因此就讀不到了。
---
### 第 3 週測驗題 測驗 `3`
以下程式碼計算 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;
}
```
補完程式碼
==P=28==
:::success
延伸問題: 解釋原理，並且提出更快的實作機制 (提示: 透過 SIMD)
:::
- [x] 第一次看的時候會嚇到，但是深入了解後會發現其觀念蠻簡單的，先有個概念，以 nibble(4-bits) 為單位，用 shift 與 XOR 來判斷此 nibble 是奇同位還是偶同位，最後再將所有 nibble 相加並取其 LSB ，若是 1 則為奇同位 0 則為偶同位。
* `x ^= x >> 1` 與 `x ^= x >> 2` 是先用 shift 來將 nibble 內的每個 bit 重疊在一起，並透過 XOR 的特性來達到兩兩消除 `b'1` 的效果，如 `b'1 XOR b'1 = b'0` ，如果最後 nibble 的 LSB 是 1 則是奇同位 0 則是偶同位， 32 bits 總共會有 8 組 nibbles 。
```
[a][b][c][d] (x)
0 1 1 0 (x) [a] 0
XOR 0 0 1 1 (x >> 1) [b] 1
----------------- [c] 1
0 1 0 1 + [d] 0
---------------
[a][b][c][d] 1 0
0 1 0 1 (x) ^ only see LSB
XOR 0 0 0 1 (x >> 2)
-----------------
0 1 0 0
^ parity bit
```
* `x = (x & 0x11111111U) * 0x11111111U` 此行的目的便是先取出所有 nibble 的 LSB 並相加在一起，並取得後面的 32 bits。
```
0001 0010 0001 ... 0100 (32-bits)
& 0001 0001 0001 ... 0001 (0x11111111U)
----------------------------
0001 0000 0001 ... 0000 <== extract all nibble's LSB
0001 0000 0001 ... 0000 (x & 0x11111111U)
* 0001 0001 0001 ... 0001 (0x11111111U)
----------------------------
0001 0000 0001 ... 0000
...
...
0001 0000 0001 ... 0000
+ 0001 0000 0001 ... 0000
------------------------------------------------
0001 0001 0001 ... 0000 ... ... ... 0000
[ out of bound ][ x only take 32 bits ]
```
* `(x >> 28) & 1` 最後再 shift right 28 bits 得到所有 nibble 相加後結果，再取其 LSB 便得到了 x 的 parity bit 了。
- [ ] SIMD
* 參考了 [Bit Twiddling Hacks](https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel) 中提到的 Compute parity in parallel 。 ~~也發現了幾題每週測驗的題目~~
```
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;
```
後來找到 [bit-interleave(SIMD ver)](https://lemire.me/blog/2018/01/09/how-fast-can-you-bit-interleave-32-bit-integers-simd-edition/) 與 [SIMD Example](https://github.com/jean553/c-simd-avx2-example) 於是想嘗試看看能不能使用 AVX 指令集來作到 parity check 。
---
### 第 2 週測驗題 測驗 `2`
[指標篇](https://hackmd.io/s/HyBPr9WGl) 提到 signal 系統呼叫的原型宣告:
```C
void (*signal(int sig, void (*handler)(int))) (int);
```
該如何解析呢？
提示: 參閱 manpage: [signal(2)](http://man7.org/linux/man-pages/man2/signal.2.html)
:::success
延伸問題: 解釋 signal(2) 的作用，並在 GitHub 找出應用案例
:::
- [x] 解析 :
* 先看 `signal(int sig, void (*handler)(int))` 有兩個參數， int 與有著 int 參數返回 void 的 function pointer ， signal 為函式名稱。
* `void (*signal(int sig, void (*handler)(int))) (int)` 則是需要 int 參數並回傳 void 的 function pointer 。
- [x]`signal(2)`
* signal 是個軟體中斷，例如 Ctrl-C ，而 `signal(2)` 函式提供了一個可以處理非同步事件的方法。
* `sig` 為 signal number ，為中斷的編號，定義在 C 函式庫的 `signal.h` 裡，變數是 SIG 開頭，像是 `SIGINT` 、 `SIGSEGV` 。
* `handler` 可以有三種值 :
1. `SIG_IGN` ，訊號忽略。
2. `SIG_DFL` ，訊號會照預設情況處理。
3. 當訊號發生時的 `handler` 就會被呼叫，此稱為 signal handler 或 signal-catching function。
4. `handler` 所傳入的參數即是 signal number 。
* 只有 `SIGKILL` 與 `SIGSTOP` 不能被忽略或是 catch 。
- [x] [TuxPLC](https://github.com/leicht/TuxPLC) 是個能從 Linux 端控制 Programable Logic Controller (PLC) 的 OpenSource 。
* 此開源程式也有使用到 `signal` 來處理中斷訊息如 :
```clike
signal(SIGTERM,SigHand);
signal(SIGINT,SigHand);
signal(SIGSEGV,SigHand);
```
* `SigHand()` 則為 :
```clike
void SigHand(int num)
{
switch (num)
{
case SIGTERM: Log(LOG_NOTICE,"receive SIGTERM\n");
Terminated=1;
break;
case SIGINT: Log(LOG_NOTICE,"receive SIGINT\n");
Terminated=1;
break;
case SIGIO: Log(LOG_INFO,"receive SIGIO\n");
//Terminated=1;
break;
case SIGSEGV: Log(LOG_CRIT,"receive SIGSEGV, program ERROR\n");
siglongjmp(jb,-1);
//Terminated=1;
//exit(1);
break;
default: Log(LOG_CRIT,"receive signal: %d\n",num);
Terminated=1;
break;
}
}
```
---
### 第 2 週測驗題 測驗 `5`
以下程式是合法 C99 程式嗎？
```C
#include <stdio.h>
int main() { return (********puts)("Hello"); }
```
請搭配 C 語言規格書解釋
繼續思考以下是否合法:
```C
#include <stdio.h>
int main() { return (**&puts)("Hello"); }
```
繼續變形:
```C
#include <stdio.h>
int main() { return (&**&puts)("Hello"); }
```
也會合法嗎？為什麼？請翻閱 C 語言規格書解說。
- [x] **是合法的**
* 根據 C99 可知，一個有 returning type 的 function designator 會被轉為 pointer to function returning type ，也就是說 `int t()` 的 function designator 會變成 `int (*t) ()` 的 pointer to function 。
> C99 [6.3.2.1] A function designator is an expression that has function type. Except when it is the operand of the sizeof operator or the unary & operator, a function designator with type ‘‘function returning type ’’ is converted to an expression that has type ‘‘pointer to function returning type ’’.
* `put()` 是個 function designator ，所以會被轉為 pointer to function :
1. `*put()` ，在前面加上 dereference of (`*`) 會使 pointer to function 變成 function designator ，但會再被轉回 pointer to function 。
2. `&put()` ，在前面加上 address of (`&`) 會讓原本的 function designator 變為 pointer to function 。
* 所以可以看到，不論在 `put()` 前怎麼加 `*` 或 `&` 最終的結果都是 pointer to function 。
---
Sign in with Wallet
Connect another wallet