2018q1 第 5 週測驗題 (上)

測驗 `1`

考慮以下程式碼，推敲其作用 (選出最符合行為的描述)

uint8_t Func32(uint32_t x) {
    return x ? Func32(x >> 1) - 1 : 32;
}

將 Func32 改寫為以下功能等價的程式碼:

uint8_t FuncI(uint32_t x)
{
    if (!x) return 32;
    int n = 1;
    if (!(x >> 16)) { n += 16; x <<= 16; }
    if (!(x >> M1)) { n +=  8; x <<=  8; }
    if (!(x >> M2)) { n +=  4; x <<=  4; }
    if (!(x >> M3)) { n +=  2; x <<=  2; }
    n = n - (x >> 31);
    return n;
}

作答區

Func32 = ?

(a) 計算對 x 的二進位表示法中，總有有幾個 bit 為 1，如果全部都是 1，那麼回傳 32
(b) 計算對 x 的二進位表示法中，總有有幾個 bit 為 0，如果全部都是 0，那麼回傳 32
(c) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32
(d) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 1，倘若 x 每個 bit 均為 1，則輸出 32
(e) 計算輸入數值 x 的二進位表示中，回傳尾巴 (低位元到高位) 有幾個 1，倘若 x 每個 bit 均為 1，則輸出 32
(f) 計算輸入數值 x 的二進位表示中，回傳尾巴 (低位元到高位) 有幾個 0，倘若 x 為 0x0，則輸出 32

M1 = ?

(a) 0xF
(b) 0xFF
(c) 0x12
(d) 0x14
(e) 0x16
(f) 0x18
(g) 0x1A

M2 = ?

(a) 0x1F
(b) 0x1E
(c) 0x1D
(d) 0x1C
(e) 0x1B
(f) 0x1A
(g) 0x10

M3 = ?

(a) 0x1E
(b) 0x1D
(c) 0x1C
(d) 0x1B
(e) 0x1A
(f) 0x10

延伸題目:

在 x86_64/Aarch32/Aarch64 ISA 中找出對應於 Func32 的指令，隨後在 GitHub 專案中找到 3 個應用案例並解說;
回顧 Week1 到 Week5 的教材和作業，提出可用對應於 Func32 (或下方 Func64) 的指令加速的案例;

測驗 `2`

延伸測驗 1，將 Func32 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 printf 函式的 %d 格式)，補完程式碼並推測其作用。

#include <stdint.h>
#include <stdio.h>

union u_qword {
    struct {
        uint32_t low;
        uint32_t high;
    } dwords;
    uint64_t qword;
};

struct udiv_result {
    union u_qword q;
    union u_qword r;
};

static inline int Func64(uint64_t val)
{
    uint32_t lo = (uint32_t) val;
    uint32_t hi = (uint32_t) (val >> 32);
    return hi ? Func32(hi) : 32 + Func32(lo);
}

static int do_udiv32(uint32_t dividend,
                     uint32_t divisor,
                     struct udiv_result *res)
{
    /* Ensure dividend is always greater than or equal to the divisor. */
    uint32_t mask = Func32(divisor) - Func32(dividend);

    divisor <<= mask;  /* align divisor */
    mask = 1U << mask; /* align dividend */
    do {
        if (dividend >= divisor) {
            dividend -= divisor;
            res->q.dwords.low |= mask;
        }
        divisor >>= 1;
    } while ((P1) && dividend);
    res->r.dwords.low = dividend;
    return 0;
}

int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res)
{
    uint64_t mask;
    uint64_t bits;

    res->q.qword = res->r.qword = 0;
    if (divisor == 0) { /* division by 0 ? */
        res->q.qword = 0xffffffffffffffffull;
        return -1;
    }
    if (divisor == dividend) {
        res->q.qword = 1;
        return 0;
    }
    if (divisor > dividend) {
        res->r.qword = dividend;
        return 0;
    }
    /* only 32 bit operands that the preconditions are fulfilled. */
    if (!(divisor >> 32) && !(dividend >> 32))
        return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res);

    bits = Func64(divisor) - Func64(dividend);
    divisor <<= bits; /* align divisor and dividend */
    mask = 1ULL << bits;
    /* division loop */
    do {
        if (dividend >= divisor) {
            dividend -= divisor;
            res->q.qword |= mask;
        }
        divisor >>= 1;
        mask >>= 1;
    } while ((P2) && dividend);

    res->r.qword = dividend;
    return 0;
}

int main()
{
    char digitbuff[20];
    char *pos = digitbuff + sizeof(digitbuff);
    union u_qword v;  /* current value */
    union u_qword nv; /* next value */
    struct udiv_result d;

    int64_t value = 0xCAFEBABE; /* Java classfile magic number */
    v.qword = (unsigned long long) value;
    while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
        /* determine digits from right to left */
        udiv64(v.qword, 10, &d);
        *--pos = d.r.dwords.low + P3;
        v.qword = d.q.qword;
    }

    do { /* process 32 bit (or reduced 64 bit) value */
        nv.dwords.low = v.dwords.low / P4;
        *--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5;
    } while ((v.dwords.low = nv.dwords.low) != 0);

    int len = digitbuff + sizeof(digitbuff) - pos;
    char *p = pos;
    while (len--)
        putchar(*p++);
    printf("\n");

    return 0;
}

作答區

Func64 的作用為？

(a) 計算對 x 的二進位表示法中，總有有幾個 bit 為 1，如果全部都是 1，那麼回傳 64
(b) 計算對 x 的二進位表示法中，總有有幾個 bit 為 0，如果全部都是 0，那麼回傳 64
(c) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64
(d) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 1，倘若 x 每個 bit 均為 1，則輸出 64
(e) 計算輸入數值 x 的二進位表示中，回傳尾巴 (低位元到高位) 有幾個 1，倘若 x 每個 bit 均為 1，則輸出 64
(f) 計算輸入數值 x 的二進位表示中，回傳尾巴 (低位元到高位) 有幾個 0，倘若 x 為 0x0，則輸出 64

P1 應該為？

(a) divisor != 0
(b) mask >>= 1
(c) divisor & mask
(d) mask != 0
(e) divisor | mask
(f) divisor ^ mask

P2 應該為？

(a) divisor != 0
(b) divisor & bits
(c) bits–
(d) mask >>= 1
(e) mask != 0
(f) divisor | mask
(g) divisor ^ mask

P3 = ?

(a) 0x0
(b) 0x1
(c) 0x10
(d) 0x11
(e) 0x20
(f) 0x21
(g) 0x30
(h) 0x31

P4 = ?

(a) 2
(b) 4
(c) 8
(d) 16
(e) 10
(f) 24

P5 = ?

(a) 0x0
(b) 0x1
(c) 0x10
(d) 0x11
(e) 0x20
(f) 0x21
(g) 0x30
(h) 0x31

延伸題目:

解釋上述程式碼，從 newlib 或 glibc 原始程式碼中找出類似上方程式碼的實作 (提示: sprintf 函式)，予以精簡並實作最小可執行的版本;
將 10 進位輸出改為 16 進位
實作浮點數輸出
上方程式碼的 0xCAFEBABE 為 magic number，舉出在真實世界中程式的實際作用 (提示: 如 malloc)

2018q1 第 5 週測驗題 (上)

測驗 1

測驗 2

測驗 `1`

測驗 `2`