# 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

:::success
延伸題目:
1. 在 x86_64/Aarch32/Aarch64 ISA 中找出對應於 `Func32` 的指令，隨後在 GitHub 專案中找到 3 個應用案例並解說;
2. 回顧 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

:::success
延伸題目:
1. 解釋上述程式碼，從 newlib 或 glibc 原始程式碼中找出類似上方程式碼的實作 (提示: `sprintf` 函式)，予以精簡並實作最小可執行的版本;
2. 將 10 進位輸出改為 16 進位
3. 實作浮點數輸出
4. 上方程式碼的 `0xCAFEBABE` 為 [magic number](https://en.wikipedia.org/wiki/Magic_number_(programming))，舉出在真實世界中程式的實際作用 (提示: 如 malloc)
:::

---