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

延伸題目：為什麼？舉出 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

延伸題目：這樣的操作可體現在哪？請在 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

延伸題目：在 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;

延伸題目：

指出這段函式在 Linux 核心原始程式碼的作用，並舉出對應的程式碼來解說;
適度改寫為正確的版本;

測驗 `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

延伸題目：解釋為何如此

測驗 `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 和非連續記憶體操作的「有品味」版本，把 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

延伸題目：在 Linux 核心原始程式碼找到類似的程式碼並解說

測驗 `7`

考慮以下透過 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);

延伸題目：

回顧 prefix-search 作業，提出資料壓縮的方案;
以上述程式碼為基礎，實作對應的 decompressor/decoder，並探究改善壓縮率的方案;

2018q1 第 8 週測驗題

測驗 1

測驗 2

測驗 3

測驗 4

測驗 5

測驗 6

測驗 7