# 2018q3 第 1 週測驗題
###### tags: `sysprog2018` `notes`
:::info
Contributor: [flawless0714](https://github.com/flawless0714)
:::
---
### 測驗`1`

int my_xor(int x, int y) { return (x | y) & (~x | ~y); }
int main() {
    int x = 3, y = 5;
    return my_xor(x, y); 
}

剛開始想到快崩潰還沒想到，結果原因是把 XOR 計算跟數位邏輯在算 XOR 一樣有進位搞在一起...，真的是沒臉說自己寫過 C 。

說明一下想法，& 左邊的 (x | y) 是先直接做 OR 運算，再來右邊的 (~x | ~y) 就是關鍵了，~ 運算子是為了讓稍後的 & 運算子積出 XOR 之運算方式，再經過 & 右邊的 (~x | ~y) 運算與左側的 (x | y)進行 & 後，即可將 XOR 運算後需要為 0 的位元 & 為 0，其他位原則保留原先 OR 後的原樣，也就是做 & 1 運算。

  [22] .got              PROGBITS         0000000000200fb8  00000fb8
       0000000000000048  0000000000000008  WA       0     0     8
  [23] .data             PROGBITS         0000000000201000  00001000
       0000000000000010  0000000000000000  WA       0     0     8
  [24] .bss              NOBITS           0000000000201010  00001010
       0000000000000018  0000000000000000  WA       0     0     8
  [25] .comment          PROGBITS         0000000000000000  00001010
       0000000000000024  0000000000000001  MS       0     0     1
  [26] .symtab           SYMTAB           0000000000000000  00001038

---

### 測驗 `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 的程式碼

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

---
測試程式碼:

    #include <stdio.h>

    struct fruit
    {
	    int color;
	    int EXP_date;
    };

    struct fruit apple;
    struct fruit orange = { .color = 0x00feff };

    int main()
    {	    
	    printf("color of the fruit: %#08x\n", orange.color);
	
	    return 0;
    }    

編譯器參數: `$ gcc -o test main.c -Wall`
readelf 參數: `$ readelf -S test`
readelf 輸出: (僅擷取部分輸出)

    Section Headers:
    [Nr] Name              Type             Address           Offset
         Size              EntSize          Flags  Link  Info  Align         
    [22] .got              PROGBITS         0000000000200fb8  00000fb8
       0000000000000048  0000000000000008  WA       0     0     8
    [23] .data             PROGBITS         0000000000201000  00001000
       0000000000000018  0000000000000000  WA       0     0     8
    [24] .bss              NOBITS           0000000000201018  00001014
       0000000000000010  0000000000000000  WA       0     0     8
    [25] .comment          PROGBITS         0000000000000000  00001014
       0000000000000024  0000000000000001  MS       0     0     1
    [26] .symtab           SYMTAB           0000000000000000  00001038
       0000000000000630  0000000000000018          27    44     8

由上方 readelf 輸出可得知 .bss section 的大小為10 bytes，而 .data section 的大小為24 bytes，再來我們將==測試程式碼中第十行==的初始化改為 `struct fruit orange;` 時，readelf 輸出則變成如下:

    Section Headers:
    [Nr] Name              Type             Address           Offset
         Size              EntSize          Flags  Link  Info  Align         
    [22] .got              PROGBITS         0000000000200fb8  00000fb8
       0000000000000048  0000000000000008  WA       0     0     8
    [23] .data             PROGBITS         0000000000201000  00001000
       0000000000000010  0000000000000000  WA       0     0     8
    [24] .bss              NOBITS           0000000000201018  00001014
       0000000000000018  0000000000000000  WA       0     0     8
    [25] .comment          PROGBITS         0000000000000000  00001014
       0000000000000024  0000000000000001  MS       0     0     1
    [26] .symtab           SYMTAB           0000000000000000  00001038
       0000000000000630  0000000000000018          27    44     8

本次輸出得知 .bss section 的大小從原本的10 bytes 增加為18 bytes，而 .data section 的大小也從原本的24 bytes 減少為16 bytes，由上下兩輸出可推論出當 struct 內有一個成員被初始化，則整個 struct 都會被配置到 .data section。