# 2018q1 第 8 週測驗題

### 測驗 `1`

考慮以下 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]`:

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 的字串處理的程式碼類似以下:

/* get the lowest hex value of a variable */
"0123456789abcdef"[x & 0xf];

:::

---

### 測驗 `3`

考慮到以下 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。

/*
 * 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` 函示的輸出為何？

#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 的資料結構宣告如下：

struct node {
    struct node *next;
    int data;
} *head;

典型新增節點到 linked list 尾端的程式碼實作如下：

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 敘述消除，改寫為以下等效的程式碼：

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`):

#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;
}

參考執行結果為:

$ ./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，並探究改善壓縮率的方案;
:::