# 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,並探究改善壓縮率的方案; :::