2018q3 第 17 週測驗題 (上)

測驗 1

考慮以下 C 程式:

int x = 2;
int main() {
    int x = 1;
    {
        extern int x;
        return x;
    }
}

執行後程式返回值 (program exit code, 用 echo $? 可得知) 為何？

作答區

• (a) 2
• (b) 1
• (c) 0
• (d) 沒定義

延伸問題: 查閱相關 C 語言規格解釋，並探討對應的資訊安全問題

---

測驗 2

考慮以下 C 程式:

typedef struct { char *key; char *value; } T1;
typedef struct { long type; char *value; } T2;
T1 a[] = {
    [1] = {
        "", ((char *) &((T2) {2, (char *) 3})),
    }
};
int main() {                             
    T2 *p = (T2 *) a[1].value;
    return (int) p->value;
}

執行後程式返回值為何？

作答區

• (a) 1
• (b) 2
• (c) 3
• (d) 標準沒有定義

延伸問題: 查閱相關 C 語言規格解釋，並探討對應的資訊安全問題

---

測驗 3

考慮以下程式碼，預期的 UNIX 終端機輸出為何？

#include <stdio.h>
unsigned long foo() {
    return (unsigned long) - 1 / 8;       
}
int main() {
    printf("%d\n", (signed) foo());
}

作答區

• (a) 1
• (b) 0
• (c) -1
• (d) 標準沒有定義

延伸問題: 從 C 編譯器的角度，解釋為何如此

---

測驗 4

考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

#include <stdint.h>
uint64_t gcd(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (K1);
    return K2;
}

補完以上程式碼。

作答區

K1 = ?

• (a) u
• (b) v
• (c) u - v
• (d) v - u
• (e) u & 1
• (f) v & 1

K2 = ?

• (a) u
• (b) v
• (c) u - v
• (d) v - u
• (e) u >> shift
• (f) v >> shift
• (g) u << shift
• (h) v << shift

---

測驗 5

承測驗 4, 透過 gcc 內建的 __builtin_ctz (Returns the number of trailing 0-bits in x, starting at the least significant bit position) 改寫程式碼如下:

#include <stdint.h>
uint64_t gcd(uint64_t u, uint64_t v) {   
    if (!u || !v) return u | v;
    int shift = __builtin_ctzll(Z1);
    u >>= __builtin_ctzll(u);
    while (v) {
        v >>= __builtin_ctzll(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v, v = t;
        }
    }
    return Z2;         
}

補完以上程式碼。

作答區

Z1 = ?

• (a) u
• (b) v
• (c) u & v
• (d) v | u
• (e) u & 1
• (f) v & 1

Z2 = ?

• (a) u
• (b) v
• (c) u - v
• (d) v - u
• (e) u >> shift
• (f) v >> shift
• (g) u << shift
• (h) v << shift

延伸問題: 解釋上述程式程式運作原理，以及在 x86_64 上透過 __builtin_ctz 改寫 GCD 對效能的提升