owned this note
owned this note
Published
Linked with GitHub
# 2018q3 Homework3 (review)
###### tags: `System-Software-2018`
contributed by < `DyslexiaS` >
## [第 1 週測驗題](https://hackmd.io/s/S1a9-YO_Q)
### 測驗 `1`
考慮以下程式碼:
```C
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 起來,就會是我們要的答案了
```clike
int my_xor(int x, int y) {
return (x | y) & (~x | ~y);
}
```
:::
---
### 測驗 `2`
考慮到以下判斷 parity bit 的程式碼,補完程式碼,N 為多少?
```clike=
#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`
考慮以下程式碼:
```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 的結構體成員==
參考資料: [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`:
```C
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 就會對了~
```C
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,最低位元組在最低位元,最高位元組在最高位元,反序排列。
![](https://i.imgur.com/ZV6AOHC.png)
#### 類似程式碼
```clike=
bool little_endian(){
unsigned int i = 1;
return *(char*)&i == 1;
}
```
:::
---
### 測驗 `3`
以下程式碼計算 parity bit:
```Clike=
#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` 就是我們要的
![](https://i.imgur.com/vKDmkEu.png)
_
2. 接下來` * 0x11111111U` 可以看成做 8 次 `x+(x<<4)`
3. 最後 8 次都 xor 完,第 28 bit 會重疊所有的數,答案會存在第 28 bit,因此 P 為 28
---
#### SIMD
:::