2022q1 Homework3 (quiz3)

contributed by < Chao-Shun-Cheng >

測驗 1

程式碼解釋

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

首先可以觀察到 ~0UL 是 0xffffffffffffffff，另外左半邊只有邏輯右移，因此可以推斷左半邊就是製造出高位的 bitmask。舉例來說，假如 h 是 60，那就代表高位的 bitmask 會是 0x0fffffffffffffff，因此可以推測出 LEFT 就是 63 - h。再來右邊就是要製造出低位的 bitmask，假如說 l 是 5，那 bitmask 就是 0xfffffffffffffff0，因此可以推測出 RIGHT 就是 l。

我認為右移 l 是多餘的，不影響結果

測驗 2

程式碼解釋

struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

參考 jim12312321 同學對於 data alignment 的解說以及Stackoverflow 的解說。其中有一個關鍵的地方 : Sequential addresses refer to sequential bytes in memory.
還沒看到這句的時候實在不懂 jim12312321 同學的意思，直到看到這個才豁然開朗。

主要就是要將最後兩個 bits 設為 0 ，另外可以觀察到 EXP1 要傳入的型態是 struct foo *，因此可以推測會用到型態轉換。因此可以得知 EXP1 就是 (struct foo *)(v & ~3)。

測驗 3

程式碼解釋

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

首先可以先觀察第 4 行，會把前 4 個與後 4 個 bit 進行交換。

x = 11110000
x >> 4 = 00001111
x << 4 = 00000000
(x >> 4) | (x << 4) = 00001111

因此可以猜測第 5 行就是兩個 bit 一組，去進行交換；第 6 行就是一個 bit 一組進行交換。另外 0xCC 就是 11001100，可以猜測出另一邊的 bitmask 要是 00110011，因此 EXP2 就是 (x & 0x55) << 2。0xAA 則是 10101010，可以猜測出另一邊的 bitmask 就是 01010101，因此 EXP3 就是 (x & 0x33) << 1。

測驗 4

程式碼解釋

#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[EXP4])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[EXP5],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

主要參考 kevinshieh0225 同學的解說

不難發現 foreach_ptr 與 foreach_int 是要把所有參數的內容指定到 i 裡面。第 6 行把 _foreach_i 當作是 index；第 7 行則去判斷有沒有超過參數範圍；最後第 8 行就是把第 index 裡的值 assign 到 i 並且進行 index++，因此可以推斷出 EXP4 就是 _foreach_i++。同理，EXP5 也是 _foreach_i++。

測驗 5

程式碼解釋

#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        EXP7;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

首先可以看到 4 ~ 15 行賄先把除數跟被除數都先轉換成正數，並將結果的正負號存在 singal 這個變數當中。

接下來看到第 18 行的 while 迴圈，會找出除數往左 shift 幾次後會比被除數大，因此可以推測出 EXP6 就是 dvs << shift。

第 22 行的 while 迴圈會去看除數是不是比被除數小，假如比較小才需要繼續計算。最後 23 ~ 26 行則是透過 shift 找出商，並減去轉成傷的部分。因此可以推測出 EXP7 就是 dvd - dvs << shift。

測驗 7

程式碼解釋

int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}

首先可以看到第 4 行，去判斷從左數來的 16 個 bits 有無 1，如果有就把結果存進去 ret 並且繼續看這 16 個 bits ( 對應到第 5 行)；第 7 行則是從這 16 個 bits 繼續去看從左數來的 8 個 bits，然後進行一樣的操作。因此可以推測出 EXP10 會是 (v > 0x3U) << 1。

可以觀察到 0xFFFFU 是 16 個 bits；0xFFU 是 8 個 bits；0xFU 是 4 個 bits；0x3U 是 2 個 bits。因此還要討論最後一個 bit，因此可以推測出 EXP11 會做出以下程式碼的行為，不過是濃縮成一行

m = (v > 0x1U);
v >>= m;
ret |= m;

因此可以知道 EXP11 就是 ret |= (v > 0x1U)

測驗 8

程式碼解釋

void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            EXP12;
        else
            EXP13;
    }
    tnode *q = *p;
    if (!q)
        return;

    if (!q->left)
        *p = q->right;
    else if (!q->right)
        *p = q->left;
    else {
        tnode **r = &q->right;
        while ((*r)->left)
            r = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

可以先參考二叉搜尋樹刪除所提及的刪除方法，會方便理解二元數的刪除原理。

首先可以看到第 4 行的 while 迴圈，會在這個迴圈找到要刪除的 node ，這邊使用指標的指標，可以找到要刪除的 node 以及他的 parent。可以知道 EXP12 是要往左邊走，EXP13 是要往右邊走，因此 EXP12 就是 p = &(*p)->left；EXP13 就是 p = &(*p)->right。

接下來就是要討論三種刪除的可能性，首先是要刪除的 node 沒有左子樹；再來是要刪除的 node 沒有右子樹，相對應的操作在 14 ~ 17 行；最後就是有左右子樹，因此只要將右子樹中最小值搬到要刪除的 node 位置。可以推測出 20 行的 while 迴圈是要找出右子樹中的最小值，因此 EXP14 就是 &(*r)->left。

測驗 9

程式碼解釋

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - MMM) & ~(NNN))

主要參考 kevinshieh0225 同學的解說

首先可以看到是要做出 16 的倍數，因此 address 的最後 4 個 bit 要可以為 0，因此可以先推測出 NNN 就是 MAX_ALIGMENT - 1。另外由於是向上對齊，所以不足 16 倍數的則要補上去，因此可以猜測出 MMM 就是 1。

測驗 10

程式碼解釋

#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

首先可以看到第 5 行的條件式，主要是用來判斷除數跟被除數是不是均為正數，另外就是利用 typeof 去看型態是不是 unsigned。假如符合條件就會進行第一個操作 ((RRR) / (__d))，不符合的話就會進行 ((SSS) / (__d))。

回顧本題目就是要進行四捨五入的操作，其中可以觀察到第 7 行的 / 在 c 語言當中是無條件捨去，因此要作一些對應的操作使其符合四捨五入的原則。

因此可以推測出 RRR 就是 __x + (__d >> 1)。另外若有負數的話就要進行減，因此 SSS 就是 __x - (__d >> 1)。