# 資訊創意研究社 - 主為演算法的ｃ
共六題，加油喔>_<

測驗期間可以上網
不得使用編譯器查看輸出

本次考試主要範圍為演算法
C99 規格書關鍵字為 C99 spec

完整好讀版請見Hackmd
https://hackmd.io/s/SyDjP5lAG

google表單填寫網址
https://goo.gl/forms/zoJe3VGStKbj4wbh1

---

# 題目 1
下列C程式碼是在實作x的y次方的計算。

int mypow(int x, int y) {

    int ret = 1;
    for (int base = x; y; base *= base, y >>= 1){
        __________ ;
    }
    return ret;
}

## 底線部份應該為何？

* `(A)` if (x ^ y) ret += base
* `(B)` if (x | 1) ret /= base
* `(C)` if (x & y) ret -= base
* `(D)` if (y & 1) ret *= base

---

# 題目 2
考慮以下 cmov (contional move) 指令的 C 程式實作:

void *cmoveq(int c, void *p1, void *p2) {
    void *r = p1;
    if (!c) r = p2;
    return r;
}

在 Intel Pentium Pro (也稱為[P6 微架構](https://en.wikipedia.org/wiki/P6_(microarchitecture))) 後引入新指令 cmoveq ,於是上面的 C 程式等價於以下 x86_64 組合語言輸出:

cmoveq:
testl %edi, %edi
cmoveq %rdx, %rsi
movq %rsi, %rax
retq

關鍵不僅在於程式碼的密度 (code density),更在於少了分支,這對於密碼學的實作非常關鍵,依據 [cryptocoding.net](http://cryptocoding.net) 的建議 [Avoid branchings controlled by secret data](https://cryptocoding.net/index.php/Coding_rules#Avoid_branchings_controlled_by_secret_data),這可避免 timing attack。請改寫上述 C 程式,使其得以在常數時間內完成 cmoveq 等價功能。欲改寫的新程式碼如下:

#include <stdint.h>
void *cmoveq(int c, void *p1, void *p2) {
    uintptr_t mask = -(!!c);
    return (void *) (((uintptr_t) C1) | ((uintptr_t) C2));
}

請補完上述 C1 和 C2 程式碼。
## C1 = ?

* `(A)` p1 | mask
* `(B)` p1 ^ mask
* `(C)` p1 & mask
* `(D)` p1 | ~mask
* `(E)` p1 ^ ~mask
* `(F)` p1 & ~mask
## C2 = ?

* `(A)` p2 | mask
* `(B)` p2 ^ mask
* `(C)` p2 & mask
* `(D)` p2 | ~mask
* `(E)` p2 ^ ~mask
* `(F)` p2 & ~mask

---

# 題目 3
考慮以下程式碼:

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    char *p, *q;
    uintptr_t pv, qv;
    {
        char a = 3;
        p = &a;
        pv = (uintptr_t) p;
    }
    {
        char b = 4;
        q = &b;
        qv = (uintptr_t) q;
    }
    if (p != q) {
        printf("%p is different from %p\n", (void *) p, (void *) q);
        printf("%" PRIxPTR " is not the same as %" PRIxPTR "\n", pv, qv);
    } else {
        printf("Surprise!\n");
    }
    return 0;
}

這段程式碼在 `macOS` 和 `GNU/Linux` 有著不同的執行輸出：

==macOS 17.5.0 / x86_64 平台上用 clang-902.0.39.1 編譯，得到以下執行輸出==

0x7ffee37fbabf is different from 0x7ffee37fbabe
7ffee37fbabf is not the same as 7ffee37fbabe

==Ubuntu Linux 17.10 / x86-64 平台用 gcc-7.2.0 編譯得到以下執行輸出==

Surprise!

>**Reference**[color=red]
>1. 在資訊安全的漏洞回報中，CWE-416: Use After Free 提及 dangling pointer 的影響
>2. 在 C11 規格書中 6.2.4:2 節提及物件的生命週期:
The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address, and retains its last-stored value throughout its lifetime. If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.

## 從以下選項中挑出最接近的描述

* `(A)` 純粹只是 C 編譯器行為的落差，實務上不需特別留意;
* `(B)` char a 和 char b 這兩個物件的生命週期僅分別在第 11 行和第 16 行有效，一旦超出 scope (作用範圍)，C 語言編譯器就會主動釋放物件，而透過 & (value-of) 運算子得到的地址自然就不再有效;
* `(C)` char a 和 char b 這兩個物件的生命週期僅分別在第 11 行和第 16 行有效，一旦超出 scope (作用範圍) 仍操作物件的話，會導致 undefined behaviour;
* `(D)` gcc 的實作不符合 C99/C11 規格描述;

---

# 題目 4
下圖為環狀 Linked list 示意圖
考慮以下程式碼，推敲程式作用並分析輸出。
假設條件：

1. malloc 總是成功而且返回的記憶體空間可讀寫
2. malloc() 得到的地址成嚴格單調遞增函數

#include <stdio.h>
#include <stdlib.h>

/* Link list node */
struct node { int data; struct node *next; };

int FuncX(struct node *head, int *data) {
    struct node *node;
    for (node = head->next; node && node != head; node = node->next)
        data++;
    return node - head;
}

struct node *node_new(int data) {
    struct node *temp = malloc(sizeof(struct node));
    temp->data = data; temp->next = NULL;
    return temp;
}

int main() {
    int count = 0;
    struct node *head = node_new(0);
    head->next = node_new(1);
    head->next->next = node_new(2);
    head->next->next->next = node_new(3);
    head->next->next->next->next = node_new(4);
    printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next->next->next->next = head;
    printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next->next->next->next->next = head->next;
    printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next = head->next->next->next->next->next->next->next->next;
    printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    printf("K5 >> %d\n", head->next->data);
    printf("count >> %d\n", count);
    return 0;
}

## FuncX 的作用是 (涵蓋程式執行行為的正確描述最多者)

* `(A)` 走訪 circular linked list 所有節點，計算節點數量並更新
* `(B)` 走訪 circular linked list 所有節點，計算節點數量並更新，回傳最後一個節點和開頭的地址距離 (offset)
* `(C)` 走訪 circular linked list 所有節點，回傳最後一個節點和開頭的地址距離 (offset)
* `(D)` 判斷是否為 circular linked list，若為 circular 則回傳非零值，其他回傳 0
* `(E)` 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值
* `(F)` 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值，過程中計算走訪的節點總數
* `(G)` 判斷是否為 circular linked list，若為 circular 則回傳非零值，其他回傳 0，過程中計算走訪的節點總數
## K1 >> 後面接的輸出為何

* `(A)` NO
* `(B)` YES
## K2 >> 後面接的輸出為何

* `(A)` NO
* `(B)` YES
## K3 >> 後面接的輸出為何

* `(A)` NO
* `(B)` YES
## K4 >> 後面接的輸出為何

* `(A)` NO
* `(B)` YES
## K5 >> 後面接的輸出為何

* `(A)` 5
* `(B)` 4
* `(C)` 3
* `(D)` 2
* `(E)` 1
* `(F)` 0
## count >> 後面接的輸出為何

* `(A)` 5
* `(B)` 4
* `(C)` 3
* `(D)` 2
* `(E)` 1
* `(F)` 0

---

# 題目 5
counting sort 只一種需線性時間的超快排序法，在排序1～100的時候更是所有演算法最快的，下面這部影片是counting sort的演算法的介紹。
{%youtube 7zuGmKfUt7s%}

下面程式碼為 counting sort 的 C 實作的變形版本：

#include <stdio.h>
#define RANGE 100

void countSort(int arr[])
{
    int out[RANGE] = {0};
    for (int i = 0; i < 16; i++){
    	out[arr[i]] = out[arr[i]] + 1;
    }

    for(int count = 0, i = 0; count < 16;){
    	if(out[i] != 0){
    		arr[count] = i;
    		@@Code1@@
    		count++;
    	}
    	else @@Code2@@;
    }
}

int main()
{
    int arr[16] = {4, 1, 0, 3, 0, 6, 1, 3, 1, 0, 5, 0, 9, 1, 0, 7};
    
    //show input
    for (int i = 0; i < 16; i++){
    	printf("%d  ", arr[i]);
    }
    printf("\n");

    countSort(arr);
    
    //show output
    for (int i = 0; i < 16; i++){
    	printf("%d  ", arr[i]);
    }
    return 0;
}

## @@Code1@@ 部份程式碼為何?

* `(A)` out[i] ++;
* `(B)` arr[i] ++;
* `(C)` out[i] --;
* `(D)` arr[i] --;
## ＠＠Code2＠＠ 部份程式碼為何?

* `(A)` i++;
* `(B)` i--;

---

# 題目 6

[Huffman coding](https://en.wikipedia.org/wiki/Huffman_coding)是一種用於無損資料壓縮的演算法，由 David A. Huffman在1952年發明。
考慮以下透過 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.

## @@@@@@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->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);

###### tags: `社團`　`題目`

---