2018q1 Homework (quiz5-1)

tags: `linyunwen` `raygoah`

contributed by <LinYunWen, raygoah>

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

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;
}

1. Func32 = ?

首先可以明顯地看到這是一個遞迴的 function ，argument 為一個 unsigned int ，而他只做一件事，如果 x 不為 0 就將自己向右平移一位 (除以二) ，然後再呼叫自己一次，否則回傳 32

因此假設我們給定

int main() {
    uint8_t result = Func32(1);
    printf("result: %" PRIu8 "\n", result);
    return 0;
}

執行過程：

改用 GDB 搭配 script 來實作遞迴程式的追蹤功能，避免用到 printf()，參見: http://kfunk.org/2014/08/29/scripting-gdb-to-execute-commands-at-particular-breakpoints/
jserv

// x = 1
Func32(1 >> 1) - 1
    0 // return 32 and go back
32 - 1 // = 31
-----------------------------------------------
    
// x = 0x0000ffff
Func32(0x0000ffff >> 1) - 1
    Func32(0x00007fff >> 1) - 1
        Func32(0x00003fff >> 1) - 1
            ...
                Func32(0x00000001 >> 1) - 1 // total has 16 layers
                    0 ? Func32(x >> 1) - 1 : 32; // return 32 and go back
                32 - 1
            ...
        19 - 1
    18 - 1
17 - 1

// result = 16

2. M1 = ?

3. M2 = ?

4. M3 = ?

在這邊我們可以先觀察到， x 若為 0 ，全部 bits 都為 0 ，因此回傳 32 很合理
看到 #5 將 x 向右平移 16 個 bits ，因此這個判斷式成立條件即為若 x 前 16 bits 都為 0 就成立，因此 n 加上 16 ，在向左平移 16 bits 回來
而這樣只檢查到前 16 bits 都為零的狀況，因此要載往小一點找，看到 #6 n 是加上 8 ，表示我要將 x 向右平移到剩下 8 bits 是保留的，故 M1 = 32-8 = 24 = 0x18
那 M2 也是一樣的道理， #7 n 是加上 4 ，表示我要將 x 向右平移到剩下 4 bits 是保留的，故 M2 = 32-4 = 28 = 0x1C
#8 n 是加上 2 ，表示我要將 x 向右平移到剩下 2 bits 是保留的，故 M3 = 32-2 = 30 = 0x1E
這邊要注意到的是因為 #4 宣告並初始化 n=1 ，因此 #9 才要在最後把第一個 bits 剪回來

Reference: uint type

延伸題目:

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

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

1. Func64 的作用為？

這裡可以清楚的看到，將 64 bits 值分為高位元和低位元區，各 32 bits ，然後再去呼叫 Func32 ，因此這個跟 Func32 很像，即是計算從最高位元，到第一個非 0 位元的 bits 個數，但是為 64 位元的版本




struct {
    uint32_t low;
    uint32_t high;
} dwords;

2. P1 應該為？

先觀察包含 P1 的 function
```
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;
}
```
- dividend 是被除數， divisor 是除數
- 此函式是用來進行 32 位元的除法， #6 中，先計算出 divisor 和 dividend 開頭皆為 0 的數字長度差距，差距為 mask
- #8 中，把除數向左移位 mask 位，為的就是讓除數對齊被除數，這樣才能達成我們平常在長除法時，從最高有效位開始做除法的目的，而在二進位中，因為只有 1 跟 0，所以除法是用減的，不需要計算相差幾倍的問題
- 參考 What does (1U << X) do?，才知道原來第九行中的 1U 是這個意思 (unsigned value 1) ，代表把第 n 個 bit 設為 1，接著同樣移位 mask 位，讓 1 能夠對齊被除數的最高有效位
- 接著便是實際除法的部份，do while 中，被除數大於除數時，就讓被除數減掉除數後更新成新的被除數，接著第 13 行所做的便是除法中差幾倍的概念，只是因為數字都是 0 和 1，所以針對 mask 中 bit 為 1 的那一位數用 OR 的方式 set 在商數中，這樣有進行被除數和除數的相減時，對應的 bit 就會被設為 1，其餘位元不變
- 而藉由上面除法的過程，可以知道 mask 因為要對齊到每次正在運算的那個位元，必須要向右移位一次，才能在每次要 set 商數時，能夠 set 到正確的 bit，所以得到 P1 必須填入 mask >> 1

3. P2 應該為？

包含 P2 的函式為 udiv64






































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;
}

udiv64 做的事情和 udiv32 相同，本質上也就是除法，但不同的地方在於這邊是針對 64 位元的數字做除法，且相比之下多了許多處理不同條件的程式碼
而注意到在實際除法的地方，多了一個變數 bits，在 32 位元的除法中，這裡 P2 的答案是 bit--，也就是判斷除到底了沒，是否該停止了，而這邊和 32 位元的地方不同，在 32 位元中，mask 同時用來 set bit 以及判斷除完了沒有

這邊的話其實我不太清楚分開成兩個變數跟只用一個變數解決的差異在哪裡，思考後覺得有可能是讓一個變數 "專心" 做好一件事，會比較不容易出錯，或是比較好維護程式碼

參考 afcidk 的提問及 jserv 老師的回答，如下:

afcidk: 感覺這樣做才是正確的，為什麼 32-bit 的版本可以讓 mask>>=1 來替代 bits 的工作呢？
jserv: 32-bit 版本的實作並不完整，其作用只是 helper function，用來實作 64-bit 版本，實際上也只有後者真的被使用

4. P3 應該為？

5. P4 應該為？

6. P5 應該為？











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);

註解中有說明 process 64 bit value as long as needed 以及 process 32 bit (or reduced 64 bit) value，然後看到程式碼的部分，要印出字元，需要將數字在 ASCII 正確輸出的話要加 49，也就是 0x31，因此 P3 以及 P5 皆為 0x31
P4 是為了把數字轉成 10 進位，因此除以 10，故 P4 選 10

解釋上述程式碼，從 newlib 或 glibc 原始程式碼中找出類似上方程式碼的實作 (提示: sprintf 函式)，予以精簡並實作最小可執行的版本;

將 10 進位輸出改為 16 進位

除以 10 的地方改為除以 16

輸出 10 以上要以 ABCDEF 代替，在 ASCII 中相當於加 0x37
TingL7












while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
    /* determine digits from right to left */
    udiv64(v.qword, 16, &d);
    *--pos = d.r.dwords.low + ((d.r.dwords.low > 9) ? 0x37 : 0x30);
    v.qword = d.q.qword;
}

do { /* process 32 bit (or reduced 64 bit) value */
    nv.dwords.low = v.dwords.low / 16;
    *--pos = (v.dwords.low - (16 * nv.dwords.low)) + (((v.dwords.low - (16 * nv.dwords.low)) > 9) ? 0x37 : 0x30);

} while ((v.dwords.low = nv.dwords.low) != 0);

實作浮點數輸出
上方程式碼的 0xCAFEBABE 為 magic number，舉出在真實世界中程式的實際作用 (提示: 如 malloc)
- Java class file 的前 4 byte 為 magic number CAFEBABE 主要做用在於辨認 file 是否是能被接受的 class file
- 參考c語言里malloc的最優實現方式是什麼？， malloc() 中也會設置 magic number，主要是因為避免 free 到沒有 malloc 的位址，藉由 magic number 設置與否就可以檢查
  TingL7