# 2018q1 第 8 週測驗題
### 測驗 `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
Reference: [Bit field](http://en.cppreference.com/w/cpp/language/bit_field)
:::success
延伸題目:為什麼?舉出 Linux 核心中用到 bit field 的原始程式碼並解說其用途
:::
---
### 測驗 `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 之間的數值,那麼:
==作答區==
A = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` 4
B = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` 4
C = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` 4
D = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` 4
:::success
延伸題目:這樣的操作可體現在哪?請在 GitHub 找出既有的開放原始碼專案來解說。
提示:某些 libc 的字串處理的程式碼類似以下:
```C
/* get the lowest hex value of a variable */
"0123456789abcdef"[x & 0xf];
```
:::
---
### 測驗 `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
:::success
延伸題目:在 C99/C11 規格書找出具體原因,並思索對應的安全議題
:::
---
### 測驗 `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. 適度改寫為正確的版本;
:::
---
### 測驗 `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
延伸題目:解釋為何如此
:::
---
### 測驗 `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,並探究改善壓縮率的方案;
:::