---
tags: linux2022
---

# 2022q1 Homework3 (quiz3)
contributed by < `eric88525` >
> [第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)

# Q1

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

1. 從最低位元到 `l` 位元需要為 0，可判斷 shift left 應該為 `l` 次，先 shift right
2. ～0UL 為 0XFFFFFFFFFFFFFFFF 且是無號數，右移 63-h 位元可讓 h 到最高位元為0
3. 做 and 運算可留下左右方的 0 ， 並保留共通的 1

+ 仔細思考後認為 `(~0UL) >> (l) << (l))` 可以寫成 `(~0UL) << (l)` ，原因是 `(~0UL) >> (l) << (l))` 後，結果為最低位元到 `l` 為 0 其餘為 1，跟`(~0UL) << (l))` 的結果一樣的

# Q2

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){(struct foo *)(v&~3), v & 3}; // return (struct fd){EXP1, v & 3};
}

+ 向下對齊 4 bytes 規律：
+ 0～3 對齊到0
+ 4～7 對齊到4
+ 8～11 對齊到 8
+ 可以觀察到只要把最後兩個位元設成0即可對齊，因此要 `&~3` 並轉形成struct 定義的型態

# Q3

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

abcd efgh
// x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
efgh abcd
// ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
ghef cdab
// x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1)
hgfe dcba

+ 透過 & mask 來讓特定位元交換

# Q4

#include <stdio.h>
#include <stdarg.h>
#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})[++_foreach_i])

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

int main()
{
    int i;
    char *p;
    
    foreach_int(i, 0, -1, 100, 0, -99)
        printf("i is %i\n", i);
    
    foreach_ptr(p, "Hello", "world")
        printf("p is %s\n", p);

    return 0;
}

+ `__VA_ARGS__` 用於將 macro 中的 `...` 展開
+ 在 for 迴圈中：
+ 用於遍歷的變數為 `_foreach_i` ， 因此要在每次迴圈結束都+1，也就是 `++_foreach_i`
+ `_foreach_i` 上限為 `sizeof((int[]){__VA_ARGS__}) / sizeof(int);` ，求得整個 int 陣列的元素數量

+ 編譯時在預處理停止，可以看到 macro 會有以下展開，在宣告 `_foreach_i` 時很巧妙的透過 () 和 ＝ 的特性，先讓 i 等於陣列的第 0 元素，接著把 0 指派給 _foreach_i

for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); (i) = ((int[]){0, -1, 100, 0, -99, 0})[_foreach_i++])
    printf("i is %i\n", i);

# Q5

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

# Q6
# Q7

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 = (v > 0x3) << 1;
    v >>= m;
    ret |= m;
    ret += v > 1;
    return ret;
}

32 bit 為 0x0000 0000 ~ 0xFFFF FFFF , 0~31 bit
+ binary search 的概念，每次都先檢查 v 是否大於$n/2$的位元數，確認是否在0~n-1 或是 n~最高位元。 n 初始為32，每當檢查完一輪 ， n 都會除以2
+ line `4-6` `7-9` `10-12` `13-15` 是做相同的事情，先檢查 v 所含位元，是否大於 v 可能有的最高位元數的一半，舉例：
+ 第4行先檢查 v 有無大於 32bits 的一半，也就是 0xffff ，第7行檢查 v 有無大於 16bits 的一半，也就是 0xff
+ 每次檢查完如果有大於一半的位元數，用 ret 來紀錄至少含有的位元數:
+ line 4 `v > 0xFFFF` 可確定最高位元至少會大於 1<<4 bit，也就是 16 bit，用 ret 紀錄下來

# Q8

void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            p = &(*p)->left; // EXP12;
        else
            p = &(*p)->right; // 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 = &(*r)->left; // r = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

+ 根據二元樹的規則，節點右側會大於當前節點，左邊則是小於。因此在 `line:5` 比較完數值後，要選擇往右或是往左走
+ EXP14 為讓 **r 在 d 節點右邊 subtree 中，往走找到最小值

+ 假設 d 為15，15 右邊 subtree 的最小數值為18

digraph{
10->5;
10->15;
15->14;
15->20;
20->18;
20->33;
15[color=blue];
18[color=red];
}

+ 把目標替換成 subtree 的最小數值

digraph{
10->5;
10->18;
18->14;
18->20;
20->33;
18[color=red]
}

# Q9

/* 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 - 1u) & ~(MAX_ALIGNMENT - 1u))

+ 題目要求為 roundup
+ ROUND_UP_TO_ALIGNMENT_SIZE(1~16) = 16
+ ROUND_UP_TO_ALIGNMENT_SIZE(17~32) = 32
+ ROUND_UP_TO_ALIGNMENT_SIZE(33~48) = 48

MAX_ALIGNMENT 的二進位為 `0x10000` ，減一後 `0x1111`，可以把不足16的部分強制進位
進位後需要保留 `0x10000` 以後的資訊，因此要 `& ~(MAX_ALIGNMENT - 1u)` ，讓0~3bit 為0，4bit 以上保留

    0x0000100
+   0x0001111
-----------
    0x0010011
&   0x1110000
-------------
    0x0010000

# Q10

#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)))                         \
            ? (((__x) + ((__d) >> 1)) / (__d))                  \
            : (((__x) - ((__d) >> 1)) / (__d));                 \
    })

+ line 3-4:
+ 先用暫存變數存 x 數值，避免在後續展開時被更動，例如輸入 x++，在後續每次被使用時數值都會變動
+ line 5: 檢查 signed 或是 unsigned，如果 unsigned 條件會為 true
+ signed int -1 = -1
+ unsigned int -1 = 4294967295
+ line 6:
+ 判斷正負號是否相同

+ line 7-8: 這段可視為 (__x / __d) +- 0.5
+ 如果 x / divisor 為負，-0.5 來達到四捨五入
+ 如果 x / divisor 為正，+0.5 來達到四捨五入