# 2019q3 Homework1 (review)
contributed by < `france5289` >

###### tags: `sysprog2019`

:::danger
注意共筆書寫的規範:
1. 中英文之間應以空白分隔;
2. 偏好的程式碼縮排是 4 spaces;
:notes: jserv
:::

## 課程簡介相關問答 1 : 有關 IEEE754

#include <stdio.h>
int main(){
    float sum = 0.0f;
    for(int i = 0; i < 10000; i++) sum += i+1;
    printf("Sum: %f\n", sum);
    return 0;
}

一開始看到這個程式碼時，很直覺的覺得這是個簡單的從1加到100000的問題，直到老師實際執行程式出錯後才發現問題並不單純。雖然當下知道是IEEE754表示法的問題，但一時之間忘記了IEEE754表示法的細節，因此這次就藉這個機會重新複習一下IEEE754表示法，並且解釋這個程式出錯的原因。
### IEEE754 解析
#### 浮點數如何表示
首先一個浮點數可以透過以下公式表示 :
$$ Value\ = \ sign \ \times \ exponet \ \times \ fraction
$$
即浮點數的實際值，等於符號位元(sign)乘上指數偏移值(exponent)再乘上分數值(fraction)。而IEEE754對浮點數的描述格式即是根據此一公式而來。

#### 如何以位元組表示浮點數
二進位浮點數是透過 *符號數值表示法* 格式儲存於電腦硬體中。
> 電腦硬體中還有其他種數值表示法嗎 ?
:::info
在電腦中數值的表示法分為 *符號數值* 、 *一補數* 與 *二補數*
現代的硬體架構均使用二補數表示法儲存整數，而浮點數則使用IEEE754表示法，其屬於符號數值表示法的一種。
詳細可參考 [解讀計算機編碼](/vOjbtew3Tn2aA0uDrmUL4Q)
:::

(source: Wikipedia)

其中各個欄位的說明如下：
- sign ( 符號位元 )
最高有效位元用來表示浮點數正負號，因此稱為sign bit
- exponent
exponent 用來表示浮點數的指數部分
- fraction
fraction 則用來表示小數部分

其中 exponent 與 fraction 欄位所佔用的位元數取決於浮點數的精確度。
若是單精度浮點數，exponent 佔8個位元而 fraction 則佔23個位元。因為 sign 永遠都佔一個位元，因此單精度浮點數總共佔32個位元。
而若是雙精度浮點數，exponent 則佔11個位元， fraction 佔52個位元，總共佔64個位元。

#### 如何將10進位小數轉成IEEE754格式
> 參考 [Decimal to IEEE 754 Floating Point Representation](https://www.youtube.com/watch?v=8afbTaA-gOQ)

以下使用263.3當做例子解釋如何將10進位小數轉成單精度IEEE754格式。
1. **將10進位小數的整數部分化為二進位**
$263_{10} \Rightarrow 100000111_{2}$
2. **將10進位小數的整數部分化為二進位**
將 $0.3$ 不斷乘上2，取運算結果中小數點左邊的 $0$ 或 $1$作為二進位表示結果。而小數點右邊的值則繼續乘上2，直到運算結果為 $0$ 或進入循環小數。
$$
0.3 \ \times \ 2 \ = \ 0.6 \\
0.6 \ \times \ 2 \ = \ 1.2 \\
0.2 \ \times \ 2 \ = 0.4 \\
0.4 \ \times \ 2 \ = 0.8 \\
0.8 \ \times \ 2 \ = 1.6 \\
0.6 \ \times \ 2 \ = 1.2 \\
....
$$
$$0.3_{10} \ \rightarrow \ 01\overline{0011}_{2}
$$
3. **進行正規化**
二進位正規化小數為 *小數點左邊只有一個位數*
因此我們將$100000111.01\overline{0011}_{2}$ 的小數點往左移，變成 $1.0000011101\overline{0011}_{2} \ \times \ 2^{8}$
4. **填入sign 、 exponent 與 fraction**
因為是正數，所以sign填入 $0$ ，而fraction則填入 $0000011101\overline{0011}$ 並填滿23個位元。至於 exponent 因為使用 exponent bias 編碼，因此必須先算出 bias 值再加上實際的指數值才能填入。
bias 值可根據以下公式而得:
$$
2^{e-1} - 1 \\
e : exponent\ 欄位的長度
$$
因此8-bit exponent 的 bias value 為 $2^{8-1} - 1 = 127$
而在第三步驟我們算出來的實際指數值8為，因此 $127\ +\ 8\ =\ 135$。接著再將 $135_{10}$ 轉為二進位無號數 $10000111_{2}$ 後，在填入 exponent 欄位。因此最終可得:
> 0 10000111 00000111010011001100110
> s exponent fraction

### 為何題組一會出錯?
:::info
我猜測是因為`int`型態轉型為`float`時，有資料上的遺失，但我仍然在想如何證明我的猜想。也許參考其他同學的共筆，能獲得一些靈感。
:::

:::warning
所以呢？你產出什麼？不要跟著智商三十的記者一樣講空話，工程師要解決問題！
:notes: jserv
:::

## 課堂測驗一

#include <stdio.h>
#define align4(x) (((x) + K) & (-4))
int main(void) {
    int p = 0x1997;
    printf("align4(p) is %08x\n", align4(p));
    return 0;
}

> K需填入何值使得4-byte alignment macro能找到給定地址的 round up alignment address?

### 思考過程
首先 $-4_{10}$ 的二進位表示法為 $11111100_{2}$ ，因此任何數與 $-4$ 做 bitwise 運算都會得到四的倍數。因此接著要思考，怎麼讓介於$1\sim4$ 或 $5\sim8$之間的數能夠round up到 4 的倍數。
首先先觀察 K=0 時，x 與 $-4$ 進行 bitwise and 的結果:
| x~10~ | x~2~ | x&(-4)~2~ | x&(-4)~10~|
|:--------:| :--------: | :--------:| :--------:|
|0| 0000 | 0000 |0|
|1| 0001 | 0000 |0|
|2| 0010 | 0000 |0|
|3| 0011 | 0000 |0|
|4| 0100 | 0100 |4|
|5| 0101 | 0100 |4|
|6| 0110 | 0100 |4|
|7| 0111 | 0100 |4|
|8| 1000 | 1000 |8|

由表格可以觀察，若想讓當 x 介於 1~3時，若要 round up 到 4 ， 則 x + k 後第三個 bit 必須為 1。而當 x 介於 5~7時，若要 round up 到 8 ， 則 x + k 後第四個 bit 必須為 1 且第三個 bit 需為 0 ， 因此 k 可以為 3 或 4。但若 k 為 4 ，則當 x 為 0 時 ， ( x + k ) & ( -4 ) 會得到 4 ， 因此 k 應該為 3 。
### Linux Kernel 中類似的 aligment 巨集
在 `/include/linux/kernel.h` 中 ， 可以找到巨集 `IS_ALIGNED(x,a)` :

#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0)

其用途為檢查 alignment 是否正確。例如若要檢查位址 `x` 是否是 4 byte alignment ， 則可透過呼叫`IS_ALIGNED(x,4)`達成。
#### 程式碼剖析
首先，若一個 address 符合 4-byte aligment，則其 address 最後兩個 bit 必須為 `00` 。
而當一個二進位數後 n 個 bit 為 `0` 時 ， 此時將該二進位數減去`1`，其後 n 個 bit 則變成 `1`。
因此若當呼叫 `IS_ALIGNED(x,4)` 時， `a = 0100`，`a - 1 = 0011`。接著將 `0011` 與 `x` 做 bitwise and ， 則相當於只保留 `x` 後面兩個 bit 的值。此時只要檢查這兩個 bit 是否為 0 即可判斷是否符合 `4-byte alignment` 。
## 課堂測驗2

#include <stdint.h>
#define INT_SIZE_OF(n) \
    ((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))

### 思考過程
首先 `sizeof()` 運算子會回傳資料型態在相對應的硬體架構下所佔的大小。
例如若在 64 位元的 x86 架構下，`sizeof(int)` 應當回傳`8`，而題目假設 `sizeof(int) = 4`。也就是在 32 位元架構下一個 int 所佔的大小。接著因為題目要求回傳要為 4 的倍數，因此回傳值的最後兩個 bit 應該要為`00`。
接著分別考慮`&`兩邊的值：
- `~(sizeof(int) + Y)`
因為要是四的倍數，回傳值的最後兩個 bit 要是`00`，且其他位數值保持不變，因此右邊這串取 not 後應該要是`11111100`。由此可得`sizeof(int) + Y`是`00000011`，而`sizeof(int) = 4`。所以 `Y` 必須為 `-1`。
- `sizeof(n) + sizeof(int) + X`
首先我試著將題目給的第一個範例帶入，可得`sizeof(n) + sizeof(int) = 17`。而為了讓答案正確，因此`X`值應該是`-1`。

> 仔細想想自己寫這兩題似乎都是在湊答案，也須應該多多參考其他同學的想法，學習用更好的方式思考。
### Linux Kernel 中類似的程式碼
在`/include/uapi/linux/kernel.h`中，可以找到巨集
`__ALIGN_KERNEL_MASK`:

#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))

此巨集用來確保 memory address alignment，其中參數 `x` 為記憶體位址，而 `mask` 則作為 mask value。其中 `mask` 應該等於 $2^n - 1$， `n` 取決於要用幾byte 做 alignment。
:::info
我不知道這樣形容 `mask` 參數是否正確，
且我也不太能夠很完整的解釋為什麼 `mask` 應該代入 $2^n - 1$。
我想若能了解 `mask` 值的意義應該能夠了解題組二的來龍去脈。
:::
## 你所不知道的 C 語言：記憶體篇
### Structure Packing v.s Padding
#### 什麼是 Padding?
在硬體架構中，CPU 為了讀取資料更加有效率，一次都是讀取一個 `word`。而 `word` 大小根據處理器架構而有所不同。若處理器為 32 bits 的處理器，則一個 `word` 即為 32 bits。
而也因此，資料在記憶體中需要對齊 `word` 大小的倍數。但在某些情況下一個變數的大小可能不足 `word` 的整數倍，因此 compiler 需要幫忙填入 empty byte 補齊不足的部分。這就是 **padding** 。
而 structure padding 則是 C compiler 在 compile C structrue 時，會檢查 structure member 所佔的記憶體空間是否為 `word` 大小的倍數，若不滿足則會進行 **structure padding**。 Compiler 所填入的 byte 基本上沒有任何用處，只是用來補齊不足的空間。
#### 什麼又是 Packing?
在某些裝置上( e.g. `嵌入式系統` )，記憶體空間十分有限，因此有時候會避免 compiler 進行 padding 的動作，
這樣就稱作 **packing** 。
我們可以透過 `# pragma pack(1)` 這個 `cpp` 指令告訴 compiler 使用 Packing 。
#### 程式碼範例
- Structure Padding

# include <stdio.h>
struct school
{
	double a;
	int b;
	char h;	
	int c;
	char d;	
};
int main()
{
	struct school students;	
	printf("size of struct %lu \n",sizeof(students));
	return 0;
}

MacdeMacBook-Pro-2:Sytem Embedded mac$ gcc structure_pack.c -o structure_pack
MacdeMacBook-Pro-2:Sytem Embedded mac$ ./structure_pack 
size of struct 24 

- Structure Packing

#include <stdio.h>
#pragma pack (1)
struct school {
    double a;
    int b;
    char h;	
    int c;
    char d;	
};

int main()
{
    struct school students;
	
    printf("size of struct %lu \n",sizeof(students));
    return 0;
}

$ gcc structure_pad.c -o structure_pad 
$ ./structure_pad
size of struct 18