# quiz8-all
contributed by <`nashi5566`, `ga639487`>
* [第八週測驗題](https://hackmd.io/s/Hknr4Rx3z)
## 問題 `1`
考慮以下 C 程式，預期輸出結果為何？
```C
#include <stdbool.h>
#include <stdio.h>
bool is_one(int i) { return i == 1; }
int main() {
struct { int a : 1; } obj = { .a = 1 };
puts(is_one(obj.a) ? "one" : "not one");
return 0;
}
```
假定 Q1 為 puts 輸出的內容，那應該為何？
==作答區==
Q1 = ?
* `(a)` one
* `(b)` not one
### Bit field
Ref: https://www.tutorialspoint.com/cprogramming/c_bit_fields.htm
:::warning
在 C99/C11 規格書找到對應的描述，適度摘錄並解說
:notes: jserv
:::
> 已經補上
> [name=nashi5566][color=#FFFFBBB]
:::warning
**C99 standard (§6.7.2.4)**
A bit-field shall have a type that is a qualified or unqualified version of _Bool, signed int, unsigned int, or some other implementation-defined type.
:::
在 `struct {int a : 1;} obj = {.a = 1 };` 的地方，原本 `int` 這個資料型態需要 4 bytes 的空間，也就是總共 32 bits ，而我們指定只用其中一個 bit 來放值。
但是因為 a 是 **signed integer** 所以 two complement 在 1 bit 的範圍內只能表示 0 ~ -1，因此結果是 `not one`
而決定 1-bit binary 1 為 -1 的是編譯器所定義，可以看到前面的引用提到 implementation-defined 這個詞，代表這個寫法結果是由實作品 (通常是指編譯器) 所決定，並且對於該定義有義務在文件內說明與告知。
像是題目的 `int` 並沒有說是 signed 或 unsigned ，那麼 bit-field 宣告之後究竟該是 signed / unsigned 是由編譯器所決定的。
:::success
延伸題目：為什麼？舉出 Linux 核心中用到 bit field 的原始程式碼並解說其用途
:::
### Linux Kernel: BUILD_BUG_ON_ZERO()
在 linux kernel.h 中有 include 一個 linux/build_bug.h ：
```C=
/*
* Force a compilation error if condition is true, but also produce a
* result (of value 0 and type size_t), so the expression can be used
* e.g. in a structure initializer (or where-ever else comma expressions
* aren't permitted).
*/
#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:(-!!(e)); }))
```
這個 macro 是用來檢查是否會有 compilation error ， e 是一個判斷式，當它經由這個 macro 結果為 true ，則可以在 compile-time 的時候被告知有錯。(因為宣告發生在 compile-time)
> 其實程式碼就算了， Linus 的註解也不是很讓人能懂
> [name=nashi][color=#FFFFBB]
然後 `int:(-!!(e))` 是代表什麼意思？
* !!(e)：對 e 做兩次 `NOT` ，確保結果一定是 0 或 1
* -!!(e)：對 !!(e) 乘上 -1 ，因此結果會是 0 或 -1
因此，當 e 這個判斷式是有錯的， !!(e) = 1，而 -!!(e) = -1，代表宣告一個 structure 中有一個 `int` ，其中 32 bits 中有 **-1 bit** 的 bit field。反之當 e 是沒有錯的，則會宣告 `int` 有 0 bit 的 bit field。
-1 的 bit field 很明顯是非法的 (constant expression must be non-negative integer)，那麼 0 bit 的 bit field 呢？
首先 zero-width bit field 有一個規定是必須 unnamed ，再來 zero-width bit field 宣告不會使用到任何空間，但是會強制 structure 中下一個 bit field 對齊到下一個 unit 的 boundary ：
:::warning
**C99 standard (§6.7.2.1)**
* The expression that specifies the width of a bit-field shall be an integer constant expression with a nonnegative value that does not exceed the width of an object of the type that would be specified were the colon and expression omitted. If the value is zero, the declaration shall have no declarator.
* A bit-field declaration with no declarator, but only a colon and a width, indicates an unnamed bit-field. As a special case, a bit-field structure member with a width of 0 indicates that no further bit-field is to be packed into the unit in which the previous bit-field, if any, was placed.
* (108) An unnamed bit-field structure member is useful for padding to conform to externally imposed layouts.
:::
舉以下例子而言 (使用的程式來自[這裡](https://stackoverflow.com/questions/13802728/what-is-zero-width-bit-field))：
```C=
struct foo {
int a:3;
int b:2;
int :0; // Force alignment to next boundary.
int c:4;
int d:3;
};
int main()
{
int i = 0xFFFF;
struct foo *f = (struct foo *)&i;
printf("a=%d\nb=%d\nc=%d\nd=%d\n", f->a, f->b, f->c, f->d);
return 0;
}
```
output 應該要是：
```C=
a=-1
b=-1
c=-4
d=0
```
也就是 a = 111 (decimal -1)、 b = 11 (decimal -1)、c = 1100 (decimal -4)、d = 000 (decimal 0) ，沒有 alignment 則是 a = 111 、b = 1 1、 c = 1 11 1、 d = 111。
但是我發現一個很奇妙的現象：
:::warning
文字訊息避免用圖片來表示！
:notes: jserv
:::
每次執行 d 的答案都不一樣欸！！！
目前正在研究中 > <
> 推測是不是放 local variable 的 stack 沒清空，但不知道怎麼看 memory layout
> [name=nashi5566][color=#FFFFBB]
:::info
我使用的編譯器版本是 gcc 5.4.0
:::
:::danger
裝新版的 gcc 和 clang 交叉比對，記得 `-O0` 和 `-O2` 的編譯選項也納入考量，之後再用 gdb 分析。
:notes: jserv
:::
### 後續
後來仔細重新思考過 padding 的方式，發現上述拿來舉例的程式碼是有漏洞的
zero-width bit-field 對齊的示意圖如下：
```
i = 1111 1111 1111 1111
padding & start from here
↓
1111 1111 1111 1111
b baaa dddcccc
|← int 32 bits →|← int 32 bits →|
```
而這裡因為宣告一個 int 的 zero-width bit-field ，所以要對齊的長度為 32 bit，c 和 d 早就已經超出 0xFFFF的範圍，指到程式中不知名的地方，才會導致 d 每次都會是不同的答案。
---
## 問題 `2`
考慮以下程式，留意到 ptr[1][2][3][4]:
```C
char ptr[5][5][5][5] = {};
int main() {
ptr[1][2][3][4] = 1;
}
```
請將 `ptr[1][2][3][4]` 改寫為功能等價的 `A [ B [ C [ D [ ptr ] ] ] ]`，其中 A, B, C, D 都是介於 1 到 4 之間的數值
首先考慮 ptr[1] = *( ptr + 1) = *(1 + ptr ) = 1[ ptr ]
ptr[1][2][3][4] = *( ptr + 1 * 125 + 2 * 25 + 3 * 5 + 4) =
*(4 + 3 * 5 + 2 * 25 + 1 * 125 + ptr) =
ptr + ((((1*5)+2)*5+3)*5)+4 = [ 4 [ 3 [ 2 [ 1 [ ptr ] ] ] ] ]
:::success
延伸題目：這樣的操作可體現在哪？請在 GitHub 找出既有的開放原始碼專案來解說。
提示：某些 libc 的字串處理的程式碼類似以下:
```C
/* get the lowest hex value of a variable */
"0123456789abcdef"[x & 0xf];
```
:::
---
```C=
void hex2(unsigned int x) {
printf("hex2: %x\n", x);
do {
char c = "0123456789abcdef" [x & 0xf];
printf("char %c for %d\n", c, x);
x >>= 4;
printf("char %c for %d\n", c, x);
} while ( x );
printf("what!");
};
```
程式在while中會根據 x & 0xf 的結果印出對應的"0123456789abcdef"
如 "0123456789abcdef" [ 0x1010 ] 會印出 a
即印出 x 最低位的hex值
---
## 問題 `3`
考慮到以下 C 程式:
```C
#include <stdint.h>
#include <stdio.h>
unsigned int ui = 0;
unsigned short us = 0;
signed int si = -1;
int main() {
int64_t r1 = ui + si;
int64_t r2 = us + si;
printf("%lld %lld\n", r1, r2);
}
```
在 LP64 的執行環境中，其輸出的形式為 "K1 K2"，那麼：
==作答區==
K1 = ?
* `(a)` -1
* `(b)` 0
* `(c)` 1
* `(d)` 4294967295
* `(e)` -2147483648
K2 = ?
* `(a)` -1
* `(b)` 0
* `(c)` 1
* `(d)` 4294967295
* `(e)` -2147483648
提示: CS:APP 3/e 第 2 章提過 integer overflow。在 C 規格書裡頭涉及 promotion
### 想法
Ref：https://wiki.sei.cmu.edu/confluence/display/c/INT02-C.+Understand+integer+conversion+rules
#### 1. Integer Conversion
:::warning
**C99 Standard (§ 6.3.1.1)**
Every integer type has an integer conversion rank defined as follows:
* No two signed integer types shall have the same rank, even if they have the same representation.
* The rank of a signed integer type shall be greater than the rank of any signed integer type with less precision.
* The rank of **long long int** shall be greater than the rank of **long int**, which shall be greater than the rank of **int**, which shall be greater than the rank of **short int**, which shall be greater than the rank of **signed char**.
* The rank of any unsigned integer type shall equal the rank of the corresponding signed integer type, if any.
* The rank of any extended signed integer type relative to another extended signed integer type with the same precision is implementation-defined, but still subject to the other rules for determining the integer conversion rank.
:::
~~不同資料型態的計算時，原則是先比 rank ，再看 signed / unsigned ，rank 大的優先， unsigned 優先~~
對不起，我上面講錯了。_(´ཀ`」 ∠) _
依照 C99 Standard ，把 integer 的 rank 排出來是：
* long long int > long int > int > short int > signed char
* unsigned int == signed int, if they are both in same precision and same size
* rank between extended signed integer types are implementation-defined
* rank of standard ones higher than the extended ones
#### 2. Integer Promotion
基本上 integer 都是照以上的規則，然而必須注意運算時有一個很特別的規則 **integer promotion** :
:::warning
If an int can represent all values of the original type, the value is converted to an int; **otherwise, it is converted to an unsigned int.** These are called the integer promotions.
:::
關於這個規則在 C99 的 48) 註腳提到：
> 48) The integer promotions are applied only: as part of the usual arithmetic conversions, to certain argument expressions, to the operands of the unary +, -, and ~ operators, and to both operands of the shift operators, as specified by their respective subclauses.
簡單來說，integer promotion 被使用在一般的算術式中 (像是使用 +, -, ~ 之類的 unary operators)，比 int 小的資料型態，譬如說 char ，會被提升成 int 的形式：
```C=
char c1, c2; // Both of them are char
c1 = c1 + c2; // result of c1 becomes to integer
```
而和 int 同 rank 的資料型態，則會在 integer promotion 後變成 unsigned 的形式：
```C=
signed int si = -1; // si & ui are at the same rank
unsigned int ui = 0;
int result = si + ui; // result is unsigned
```
:::warning
在 C99/C11 規格書找出對應的描述並解讀
:notes: jserv
:::
> 已經補上
> [name=nashi5566][color=#FFFFBBB]
因此第1題：
* 檢查兩者之間的 rank ，是一樣的，但是因為 integer promotion 的關係 si 提昇成 unsigned → decimal 4294967295
第2題：
* us 為 short ，rank 比 signed int 的 si 低，us 變換成 signed int 形式→ decimal -1
> 強者我朋友 JA 問我，integer promotion 究竟是 assign 之前被 cast ，還是 assign 之後被 cast，因為 binary 情況下就只是 0xFFFF + 0x0000，要怎麼看出來？覺得這個問題很神奇所以紀錄下來思考。
>
> 這裡做了一個實驗，故意寫一個會出錯的程式碼由 compiler diagonsis 來看它到底是什麼 data type ：
> ```C=
> void test(int *a){};
> char a, b;
> test(a+b);
> ```
> 而 compiler 的結果是：
>```C=
> >> expected int* but argument is of type int
>```
> 由此可知，運算的當下就會發生 integer promotion
> [name=nashi5566][color=#FFFFBBB]
:::success
延伸題目：在 C99/C11 規格書找出具體原因，並思索對應的安全議題
:::
### Integer Overflow d(d＇∀＇)
Ref：http://projects.webappsec.org/w/page/13246946/Integer%20Overflows
Integer Overflow 發生在進行運算時，結果的數字超過儲存結果的變數的資料型態，例如算出來是 64-bit 的數字，但是 result 是 type of `int` 。
這時會發生一個叫作 **wraparound** 的現象，當數字超過最大值，多出來的數字會從最小值重新開始，就像時鐘一樣，早上超過 12:00 時，13:00 時指針會指向 1 重新開始。
回到程式來，以 8-bit signed integer 而言，它的範圍介在 -128 ~ 127 之間，如果程式中存了一個數字 127 ，我們對其 +1 ，直觀來想答案應該是 128 ，但是因為 128 超過這個資料型態的範圍，反而會變成 -128 。反過來如果數字太小也會有問題，叫作 Underflow ，在範圍的最小值的地方發生 wraparound 。
### SSH CRC32 Weakness
---
## 問題 `4`
以下程式碼改寫自 Linux 核心原始程式碼，請對照註解 (預期功能)，指出實作上的問題，假設輸入 `value` 不會超過 32-bit。
```C=
/*
* Convert a signed n-bit integer to signed 32-bit integer.
* Common cases are done through the compiler,
* the screwed things has to be done by hand.
*/
static int32_t snto32(uint32_t value, unsigned n) {
switch (n) {
case 8: return ((int8_t) value);
case 16: return ((int16_t) value);
case 32: return ((int32_t) value);
}
return value & (1 << (n - 1)) ? value | (-1 << n) : value;
}
```
==作答區==
Q2 = ?
* `(a)` 第 10 行總是輸出錯誤結果;
* `(b)` 第 6 到 8 行的轉型會導致 undefined behavior;
* `(c)` `value` 不該用 `uint32_t`，這會導致轉型過程中的資料遺失;
* `(d)` 位移非正值會導致 undefined behavior;
:::success
延伸題目：
1. 指出這段函式在 Linux 核心原始程式碼的作用，並舉出對應的程式碼來解說;
2. 適度改寫為正確的版本;
:::
---
位移非正值時會發生問題，因為邏輯位移和算術位移得出的結果不同。
舉例 : -1 為 1111 1111
邏輯右移一位時為: 0111 1111
算數右移一位時為: 1111 1111
## 問題 `5`
考慮以下程式碼，在 x86_64 搭配 glibc 實作，`printf` 函示的輸出為何？
```C
#include <stdio.h>
union some {
int i; float f;
};
int func(union some *up, float *fp) {
up->i = 123; *fp = -0.0;
return up->i;
}
int main() {
union some u;
printf("%d\n", func(&u, &u.f));
return 0;
}
```
提示: C99 規格書 `6.5.2.3` 提到:
> If the member used to access the contents of a union object is not the same as the member last used to store > a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type.
==作答區==
K3 = ?
* `(a)` -1
* `(b)` 0
* `(c)` 1
* `(d)` 4294967295
* `(e)` -2147483648
:::success
延伸題目：解釋為何如此
:::
Union 是一種將不同 data types 儲存在同一個記憶體空間的特殊自訂型別， union 一次只會儲存一個變數資料。
所有在 union 宣告的變數會共享同一個記憶體空間，而且會已宣告的變數型態 size 最大的變數空間作為記憶體空間。
修改任一成員的值皆會影響到其他成員的值，在同一時間內只能保存一個成員的值。
在題目中 int 與 float 皆為 4 bytes
func中給定 `up->i = 123;` 此時記憶體空間為 0x0000007b
接下來指定 `*fp = -0.0;` 記憶體空間變為 0x80000000
最後 printf 出return的 up->i ，此時記憶體空間為修改過後的0x80000000
在2補數表示法中即為 -2147483648
---
## 問題 `6`
考慮到某個 linked list 的資料結構宣告如下：
```C
struct node {
struct node *next;
int data;
} *head;
```
典型新增節點到 linked list 尾端的程式碼實作如下：
```C
void insert(struct node *new_node) {
struct node *node = head, *prev = NULL;
while (node && node->data < new_node->data) {
prev = node;
node = node->next;
}
new_node->next = node;
if (!prev)
head = new_node;
else
prev->next = new_node;
}
```
其中 `new_node` 是已配置的節點記憶體位址。
請比照 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) 的「有品味」版本，把 if-else 敘述消除，改寫為以下等效的程式碼：
```C
void insert(struct node *new_node) {
struct node **link = &head;
for (; *link && (*link)->data < new_node->data; Z1)
;
Z2;
*link = new_node;
}
```
補完欠缺的程式碼 (Z1 和 Z2)
==作答區==
Z1 = ?
* `(a)` link = link->next
* `(b)` *link = link->next
* `(c)` link = *(link->next)
* `(d)` link = &(*link)->next
Z2 = ?
* `(a)` new_node->next = *link
* `(b)` (*new_node)->next = *link
* `(c)` new_node->next = link
* `(d)` *new_node->next = *link
Reference:
* [Linus on Understanding Pointers](https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/)
:::success
延伸題目：在 Linux 核心原始程式碼找到類似的程式碼並解說
:::
---
## 問題 `7`
考慮以下透過 [Huffman coding](https://en.wikipedia.org/wiki/Huffman_coding) 進行資料壓縮的程式碼 (`huff.c`):
```C
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define ASCII_SIZE 128
typedef struct _node {
struct _node *left, *right;
unsigned weight;
char data;
} node_t;
typedef struct {
unsigned size;
node_t *array[ASCII_SIZE];
} min_heap_t;
typedef struct {
int arr[ASCII_SIZE / 4];
int length;
char data;
} pair_t;
static inline void swap_node(node_t **a, node_t **b) {
node_t *t = *a;
*a = *b;
*b = t;
}
static void shift_up_2(min_heap_t *heap) {
int i = 0;
while (i < heap->size) {
(heap->array)[i] = (heap->array)[i + 2];
(heap->array)[i + 1] = (heap->array)[i + 3];
i++;
}
heap->size -= 2;
}
static void add_to_heap(node_t *to, min_heap_t *heap) {
int pos = heap->size++;
heap->array[pos] = to;
if (heap->size > 2) {
while ((heap->array[pos - 1])->weight > (heap->array[pos])->weight) {
swap_node(&(heap->array[pos - 1]), &(heap->array[pos]));
if (--pos == 0)
break;
}
}
}
static node_t *combine_node_ts(node_t *lighter, node_t *heavier) {
node_t *new_node = calloc(1, sizeof(node_t));
new_node->left = lighter;
new_node->right = heavier;
new_node->weight = lighter->weight + heavier->weight;
return new_node;
}
static node_t *build_hufftree(min_heap_t *heap) {
while (heap->size > 1) {
add_to_heap(combine_node_ts(heap->array[0], heap->array[1]), heap);
shift_up_2(heap);
}
return heap->array[0];
}
void encode(FILE *in, FILE *out, pair_t *pairs) {
int curr_size = 0;
unsigned buffer = 0;
for (;;) {
int ch = fgetc(in);
if (ch == EOF)
break;
int i = 0;
while (i++ < pairs[ch].length) {
buffer <<= 1;
buffer += (pairs[ch].arr)[i];
curr_size++;
if (curr_size == 8) {
fwrite(&buffer, 1, 1, out);
curr_size = 0;
buffer = 0;
}
}
}
while (curr_size < 8) {
buffer <<= 1;
curr_size++;
}
rewind(in);
fwrite(&buffer, 1, 1, out);
fclose(out);
}
void build_pairings(node_t *root, int arr[], int top, pair_t *pairs) {
if (root->left) {
arr[top] = 0;
XXA;
}
if (root->right) {
arr[top] = 1;
XXB;
}
if (!(root->left) && !(root->right)) {
uint8_t index = root->data;
for (int i = 0; i < top; i++)
pairs[index].arr[i] = arr[i];
pairs[index].length = top;
pairs[index].data = root->data;
}
}
min_heap_t *scan_file(FILE *in) {
node_t *dictionary = calloc(ASCII_SIZE, sizeof(node_t));
min_heap_t *heap = calloc(1, sizeof(min_heap_t));
int ch;
for (;;) {
if ((ch = fgetc(in)) == EOF)
break;
dictionary[ch].weight++;
}
for (ch = 0; ch < ASCII_SIZE; ch++) {
if (dictionary[ch].weight == 0)
continue;
dictionary[ch].data = ch;
add_to_heap(&(dictionary[ch]), heap);
}
rewind(in);
return heap;
}
int main(int argc, char *argv[])
{
if (argc != 2) {
printf("Usage: %s <input file>\n", argv[0]);
return -1;
}
FILE *in = fopen(argv[1], "r");
FILE *out = fopen("out", "wb");
int arr[ASCII_SIZE];
min_heap_t *data_heap = scan_file(in);
pair_t *pairs = calloc(ASCII_SIZE, sizeof(pair_t));
build_pairings(build_hufftree(data_heap), arr, 0, pairs);
printf("Compressing...\n");
encode(in, out, pairs);
FILE *read_out = fopen("out", "r");
fseek(in, 0L, SEEK_END);
fseek(read_out, 0L, SEEK_END);
int before = ftell(in);
int after = ftell(read_out);
double efficiency = 100 - (((double) after / (double) before) * 100);
printf("Achieved %f %% compression.\n", efficiency);
fclose(read_out);
fclose(in);
free(data_heap);
free(pairs);
return 0;
}
```
參考執行結果為:
```shell
$ ./huff huff.c
Compressing...
Achieved 40.820361 % compression.
```
請嘗試補完上述 `build_pairings` 函式裡頭透過遞迴呼叫的敘述 `XXA` 和 `XXB`。
==作答區==
XXA = ?
* `(a)` build_pairings(root->left, arr, top - 2, pairs);
* `(b)` build_pairings(root->left, arr, top - 1, pairs);
* `(c)` build_pairings(root->left, arr, top, pairs);
* `(d)` build_pairings(root->left, arr, top + 1, pairs);
* `(e)` build_pairings(root->left, arr, top + 2, pairs);
XXB = ?
* `(a)` build_pairings(root->right, arr, top - 2, pairs);
* `(b)` build_pairings(root->right, arr, top - 1, pairs);
* `(c)` build_pairings(root->right, arr, top, pairs);
* `(d)` build_pairings(root->right, arr, top + 1, pairs);
* `(e)` build_pairings(root->right, arr, top + 2, pairs);
:::success
延伸題目：
1. 回顧 prefix-search 作業，提出資料壓縮的方案;
2. 以上述程式碼為基礎，實作對應的 decompressor/decoder，並探究改善壓縮率的方案;
:::
### 想法：
#### 0. 忘記 Huffman Tree 怎麼建了所以先看一下演算法聖經
假設有一個檔案，裡面出現過的字元只有 a - f 共 100000 個，計算完每個出現的字數次數之後，之後我們可以採取兩種方式來設計 binary character code ：
| char | a | b | c | d | e | f |
|------|---|---|---|---|---|---|
| freq.| 45| 13| 12| 16| 9 | 5 |
|fixed-len|000| 001 | 010 | 011 | 100|101|
|varaible-len| 0 | 101|100|111|1100|1101|1100|
1. fixed-length code
就照順序編碼，只不過這裡共有6個數字，必須使用 3-bit binary code 才能完全表示，整個檔案大小共需 $3 * 100000 = 300000$ bits
2. variable-lengrh code
前者的改良，出現次數愈多的，編碼的 bit 長度愈短，出現次數愈少的編碼的 bit 長度愈長，所以 a 只需要一個 bit ， f 需要 4 個 bit，整個檔案共需 $(45*1 + 13*3 + 12*3 +16*3+9*4+5*4)*100000 = 224000$ bits
```
(100)
/ \
(a/45) (55)
/ \
/ \
/ (30)
/ / \
(25) (d/16) (14)
/ \ / \
(b/13) (c/12) (e/9) (f/5)
```
#### 1. 首先先了解各個程式
* min_heap_t
* 這裡使用 min heap 的結構來儲存目前有輸入的 char 出現的頻率，因為 ASCII code 目前有 128 種字元，所以宣告一個大小為 128 bytes 的 array 來存放
* size 指的是目前 heap 裡面有的最大字元 ASCII code
* shift_up_2
*
* add_to_heap
Sign in with Wallet
Connect another wallet