# 資訊創意研究社 - 主為演算法的c
共六題,加油喔>_<
測驗期間可以上網
不得使用編譯器查看輸出
本次考試主要範圍為演算法
C99 規格書關鍵字為 C99 spec
完整好讀版請見Hackmd
https://hackmd.io/s/SyDjP5lAG
google表單填寫網址
https://goo.gl/forms/zoJe3VGStKbj4wbh1
---
# 題目 1
下列C程式碼是在實作x的y次方的計算。
```clike=
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 程式實作:
```clike=
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 組合語言輸出:
```clike=
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 等價功能。欲改寫的新程式碼如下:
```clike=
#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
考慮以下程式碼:
```clike=
#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 示意圖
![環狀 Linked list](https://lh5.googleusercontent.com/2ufavCzwIR1NM2oxkP24H_k-kS2oOkLEnUjCChDR6f88RFzBAYqIh9n_xACauQ02ooE8q2yabg=w651)
考慮以下程式碼,推敲程式作用並分析輸出。
假設條件:
1. malloc 總是成功而且返回的記憶體空間可讀寫
2. malloc() 得到的地址成嚴格單調遞增函數
```clike=
#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 實作的變形版本:
```clike=
#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):
```clike=
#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: `社團` `題目`
---