# 2018q3 Homework3 (review)
###### tags: `System-Software-2018`
contributed by < `DyslexiaS` >

## [第 1 週測驗題](https://hackmd.io/s/S1a9-YO_Q)
### 測驗 `1`

考慮以下程式碼:

int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3  OP4 y); }
int main() {
    int x = 3, y = 5;
    return my_xor(x, y); 
}

`my_xor` 嘗試不用 XOR 運算子做出等效的 XOR 運算，其中 OP1, OP2, OP3, OP4 都是 operator，請補完實作。
::: success
#### 解釋
1. 先看 `(x | y)` 與 `x ^ y` 的差別：
發現 `(x | y)` 只有在 x = 1, y = 1 時答案等於 1 和 XOR 不同，因此要把這種情況找出來並將其值改成 0

2. `(OP2 x OP3 OP4 y)`
`（~x）｜（~y）` 只有原本 x = 1, y = 1 的值會是 0 ,因此只要把這個值 And 起來，就會是我們要的答案了

int my_xor(int x, int y) { 
    return (x | y) & (~x | ~y); 
}

:::

---

### 測驗 `2`

考慮到以下判斷 parity bit 的程式碼，補完程式碼，N 為多少？

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

:::success
#### 解釋
1. 先觀察 24 行 return 之前的處理 `return table[num & 0xff]; ` 可以發現最後只須留下後面 8 bits 便可進行查表得到答案
2. 看到 19 行 `num = num ^ (num >> max)` ，一開始 max = 16，因此 32 bits 的 num 會向右平移 16 bits，在和自己做 XOR，依據 XOR 的結果，不會改變到 1 個數的奇偶，並消掉兩個 1 的狀況，`num [31:16] XOR num [15:0]` 完後，num [15:0] 的 parity bit 會等價於 num [31:0] ，因此可以得知==N = 2==
:::
#### 實做循環冗餘校驗
[CRC概念](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97)

---
## [第 2 週測驗題](https://hackmd.io/s/BJA6LjbK7)

---
## [第 3 週測驗題](https://hackmd.io/cCa9LSvQSey1R7XgP47Slg?both)

### 測驗 `1`

考慮以下程式碼:

#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 換為以下:

    printf("Address of t.x is %p", &t.x);

會發生什麼事？
==編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員==

參考資料: [Portable Bit Fields in packetC](https://link.springer.com/content/pdf/10.1007/978-1-4302-4159-1_34.pdf)

:::success
#### 解釋原因，並且找出 C99/C11 規格書對應的描述
>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==

>6.5.32
>The operand of the unary & operator shall be either a function designator, the result of a [] or unary * operator, or an lvalue that designates an object that is ==not a bit-field== and is not declared with the register storage-class specifier.

:::

---

### 測驗 `2`

考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:

int main() {
    union { int a; char b;
    } c = { .a = K1 };     // K1 = 1
    return c.b == K2;      // K2 = 1
}

一開始覺得 K1 = 254, K2 = 254 也是正確答案，但把 c.b print 出來，發現 c.b = -2，也就是說 char 其實是有 signed(範圍 -128~127)，因此把 char 改成 unsigned char 就會對了～

int main() {
    union { int a; unsigned char b;
    } c = { .a = 254 };  
    return c.b == 254;
}

:::success
#### 運作原理

1. 如果是Big Endian的系統：
存到記憶體會變成 0x00 0x00 0x00 0x01，最高位元組在位址最低位元，最低位元組在位址最高位元，依次排列。
2. 如果是Little Endian的系統：
存到記憶體會變成 0x01 0x00 0x00 0x00，最低位元組在最低位元，最高位元組在最高位元，反序排列。


#### 類似程式碼

bool little_endian(){
    unsigned int i = 1;
    return *(char*)&i == 1;
}  

:::

---

### 測驗 `3`

以下程式碼計算 parity bit:

#include <stdint.h>
int parity(uint32_t x)
    x ^= x >> 1;
    x ^= x >> 2;
    x = (x & 0x11111111U) * 0x11111111U;
    return (x >> P) & 1;
}

:::success
#### 解釋原理，並且提出更快的實作機制 (提示: 透過 SIMD)
> xor 結果：奇數個 1 為 1,偶數個則為 0
1. 做完 3, 4 行之後，$(4n+1)$ bit $（7\geq n\geq0）$ 會是每 4 個 bit 做 xor，以 4 bit 為例：
紅色框框內是 x 做完運的結果
最後 4 bit 會是 `a^b^c^d` 就是我們要的

_
2. 接下來` * 0x11111111U` 可以看成做 8 次 `x+(x<<4)`
3. 最後 8 次都 xor 完，第 28 bit 會重疊所有的數，答案會存在第 28 bit，因此 P 為 28

---
#### SIMD
:::