2019q3 Homework2 (quiz2)

contributed by < ArielWu0203 >

tags: linux_2019

• 作業要求

Test 1

考慮下方檔案 4thought.c 是 ACM-ICPC 題目 4 thought 的一個解法，假設程式的輸入符合 4 thought 的描述，請補完程式碼:

#include <stdbool.h>
#include <stdio.h>

enum {
    opType1 = 0x1 << 0, opType2 = 0x1 << 1,
    opType3 = 0x1 << 4, opType4 = 0x1 << 5,
};

static int operate(int op, int a, int b) {
    switch (op) {
    case opType1: return a + b;
    case opType2: return a - b;
    case opType3: return a * b;
    case opType4: return (int) a / b;
    }
    return 0;
}

static char op_to_char(int op) {
    return "+-*/?"[op - 1];
}
static int op_to_prio(int op) {
    return ((int[]){opType1, opType2, opType3, opType4, -1})[op - 1];
}

static int calc(int op1, int op2, int op3) {
    op1 = op_to_prio(op1);
    op2 = op_to_prio(op2);
    op3 = op_to_prio(op3);

    bool p1 = (op1 & 0x0F) == 0;  // = 1 for * or /
    bool p2 = (op2 & 0x0F) == 0;  // else = 0
    bool p3 = (op3 & 0x0F) == 0;

    // (4 + 4 + 4 + 4) or (4 / 4 / 4 / 4)
    if ((p1 == p2) && (p2 == p3))
        return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
    // (4 + 4 + 4 / 4)
    else if ((p1 == p2) && (p2 < p3))
        return operate(op2,operate(op1,4,4),operate(op3,4,4));
    // (4 / 4 / 4 + 4)
    else if ((p1 == p2) && (p2 > p3))
        return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
    // (4 + 4 / 4 / 4)
    else if ((p1 < p2) && (p2 == p3))
        return operate(op1, 4, operate(op3, operate(op2, 4, 4), 4));
    // (4 / 4 + 4 + 4)
    else if ((p1 > p2) && (p2 == p3))
        return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
    // (4 + 4 / 4 + 4)
    else if ((p2 > p1) && (p1 == p2))
        return operate(op3, operate(op1, 4, operate(op2, 4, 4)), 4);
    // (4 / 4 + 4 / 4)
    else if ((p1 > p2) && (p1 == p2))
        return operate(op2, operate(op1, 4, 4), operate(op1, 4, 4));

    return 0;
}

int main(void) {
    int n;
    scanf("%d", &n);
    int sol[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &sol[i]);

    bool validSolution = false;
    for (int i = 0; i < n; i++) {
        for (int op1 = 4; op1 > 0; op1--) {
            for (int op2 = 4; op2 > 0; op2--) {
                for (int op3 = 4; op3 > 0; op3--) {
                    int sol_checked = calc(op1, op2, op3);
                    if (sol_checked == sol[i]) {
                        validSolution = true;

                        char op1char = op_to_char(op1);
                        char op2char = op_to_char(op2);
                        char op3char = op_to_char(op3);

                        printf("4 %c 4 %c 4 %c 4 = %d\n", op1char, op2char,
                               op3char, sol[i]);
                        op1 = -1; op2 = -1; op3 = -1;
                        break;
                    }
                }
            }
        }
        if (!validSolution)
            printf("no solution\n");
        validSolution = false;
    }
    return 0;
}

延伸問題:

1. 解釋程式運作的原理和推敲背後的思路;
2. 探討 4 thought 組合出來的數值分佈，並且透過數論解釋;
3. 提出得以改善上述程式碼執行效率的方案，著手分析和實作;

Test 2

考慮以下程式碼 (fitbits.c) 可檢驗輸入的整數 x 是否可用 n 個位元來表示，例如 (x = 4, n = 9) 要回傳 true, 當 (x = 4, n = 2) 回傳 false。

#include <stdbool.h>
bool fit_bits(int x, int n) {
    int mask = (-1) & (1 << (n-1));
    int sign = 1 & (x >> 31);
    x = (x & mask) >> (n-1);
    x = ~((sign-1)^x); 
    return (bool) !x;
}

延伸問題: 在重視資訊安全的專案中，找出類似用法的程式碼，予以解說並進行相關 information leaks 的實驗

Test 3

考慮以下程式碼 (is-less-equal.c) 可檢驗輸入的整數 x 和 y，是否存在

$x<=y$ 的關係。例如 (x = 4, n = 4) 要回傳 true, 當 (x = 14, n = 9) 回傳 false。

#include <stdbool.h>
bool is_leq(int x, int y) {
    int sign_x = (x>>31) & 1;
    int sign_y = (y>>31) & 1;
    int diff = sign_x ^ sign_y;
    int diff_leq = diff & sign_x; // different sign & x is negative
    int leq = (!diff) & !(y + (~x+1) >> 31) ; // same sign
    return (leq | diff_leq);
}

延伸問題: 在重視資訊安全的專案中，找出類似用法的程式碼，予以解說並進行相關 information leaks 的實驗

Test 4