2022q1 Homework3 (quiz3)

contributed by < ganoliz >

測驗一

在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:

• GENMASK(6, 4) 產生
  ${01110000}_2$
• GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)
  已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:

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

請問，
LEFT = ?
RIGHT = ?

我們可以知道 ~0UL 的值是 0 ~ 64 bits 的值都為 1 ，然後我們可以將這個 GENMASK 巨集拆成兩個部分:
(~0UL) >> (LEFT) 與 (~0UL) >> (l) << (RIGHT) 兩個部分。在假設為"非邏輯位移"的情況下(而且這裡是 unsigned long)，那麼答案為 LEFT = 63 - h RIGHT = l

(((~0UL) >> (63 - (h))) & ((~0UL) >> (l) << (l)))

延伸問題:

1. 解釋上述程式碼運作原理
2. 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
3. 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

測驗二

考慮以下程式碼:

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

函式 fo_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 struct foo; 運用〈你所不知道的 C 語言：指標篇〉提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。
請問，
EXP1= ?

參考<jim12312321> 對於記憶體對齊的描述:
向上對齊(對 4 bytes 或 8 bytes 對齊):

• 對記憶體的位置最後 2 個 bits 做 clear 的動作才能對齊
• 對記憶體第3個 bit (
  $2^2$) + 1

未 alignment 前起始位置 :

$0x{01}_{16}$
alignment 後 :

$0x{04}_{16}$

向下對齊:

• 對記憶體的位置最後 2 個 bits 做 clear 的動作。

未 alignment 前起始位置 :

$0x{01}_{16}$
alignment 後 :

$0x{00}_{16}$

因此在對齊，我們可以知道(注意向下對齊是往記憶體位置的下面對齊)

//EXP 1 :
return (struct fd){ (struct *foo)(v & ~3), v & 3};

延伸問題:

1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

測驗三

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. Reverse Bits 的描述。

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

請問，
EXP2 = ?
EXP3 = ?

這裡就是老師 C語言 bitwise 講座提到的內容，基本上這段程式碼就是透過shift的方式一對一對的把高低位元交換。首先最高四個位元與最低四個位元交換。接著是 4 bits 的高兩個位元與低兩個位元交換，
因此

x = ((x & 0xCC) >> 2 | (x & 0x33) << 2)
x = ((x & 0xaa) >> 1)| (x & 0x55) << 1)

測驗四

延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:

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

預期輸出如下:

i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world

對應的巨集定義:

#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__})))

請問，
EXP4 = ?
EXP5 = ?

根據巨集，我們可以進行拆解，在 foreach_int 迴圈裡， ( i ) = ((int []){VA_ARGS})[0] ，就是指目前在 後面參數中的第零個位置的值，因此我們要更新的值是 _foreach_i

...;...; (i) = ((int []){__VA_ARGS__, 0}[++_foreach_i]) // 原本寫 _foreach_i++ 是錯誤的，要先加再賦值

延伸問題:

1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗五

針對 LeetCode 29. Divide Two Integers，以下是可能的實作:

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

EXP6 = ?
EXP7 = ?

EXP6: while (dvd > (dvs << shift)) // 原本寫 1 << shift 會有 error 的情況

EXP7: dvd -=  dvs << shift;

延伸問題:

1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論

測驗六

針對 LeetCode 149. Max Points on a Line，以下是可能的實作:

#include <stdbool.h>
#include "list.h"

struct Point {
    int x, y;
};

struct point_node {
    int p1, p2;
    struct list_head link;
};

static bool can_insert(struct list_head *head, int p1, int p2)
{
    struct point_node *pn;
    list_for_each_entry (pn, head, link)
        return EXP8;
    return true;
}

static int gcd(int x, int y)
{
    while (y) {
        int tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

static int maxPoints(struct Point *points, int pointsSize)
{
    if (pointsSize <= 2)
        return pointsSize;

    int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
    int *dup_cnts = malloc(pointsSize * sizeof(int));
    int *hori_cnts = malloc(pointsSize * sizeof(int));
    int *vert_cnts = malloc(pointsSize * sizeof(int));
    int *slope_cnts = malloc(slope_size * sizeof(int));
    memset(hori_cnts, 0, pointsSize * sizeof(int));
    memset(vert_cnts, 0, pointsSize * sizeof(int));
    memset(slope_cnts, 0, slope_size * sizeof(int));

    for (i = 0; i < pointsSize; i++)
        dup_cnts[i] = 1;

    struct list_head *heads = malloc(slope_size * sizeof(*heads));
    for (i = 0; i < slope_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (i = 0; i < pointsSize; i++) {
        for (j = i + 1; j < pointsSize; j++) {
            if (points[i].x == points[j].x)
                hori_cnts[i]++, hori_cnts[j]++;

            if (points[i].y == points[j].y)
                vert_cnts[i]++, vert_cnts[j]++;

            if (points[i].x == points[j].x && points[i].y == points[j].y)
                dup_cnts[i]++, dup_cnts[j]++;

            if (points[i].x != points[j].x && points[i].y != points[j].y) {
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int tmp = gcd(dx, dy);
                dx /= tmp;
                dy /= tmp;
                int hash = dx * dy - 1333 * (dx + dy);
                if (hash < 0)
                    hash = -hash;
                hash %= slope_size;
                if (can_insert(&heads[hash], i, j)) {
                    struct point_node *pn = malloc(sizeof(*pn));
                    pn->p1 = i;
                    pn->p2 = j;
                    EXP9;
                }
            }
        }
    }

    for (i = 0; i < slope_size; i++) {
        int index = -1;
        struct point_node *pn;
        list_for_each_entry (pn, &heads[i], link) {
            index = pn->p1;
            slope_cnts[i]++;
        }
        if (index >= 0)
            slope_cnts[i] += dup_cnts[index];
    }

    int max_num = 0;
    for (i = 0; i < pointsSize; i++) {
        if (hori_cnts[i] + 1 > max_num)
            max_num = hori_cnts[i] + 1;
        if (vert_cnts[i] + 1 > max_num)
            max_num = vert_cnts[i] + 1;
    }
    for (i = 0; i < slope_size; i++) {
        if (slope_cnts[i] > max_num)
            max_num = slope_cnts[i];
    }

    return max_num;
}

EXP8 = ?
EXP9 = ?

延伸問題:

1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行

測驗七

考慮 ilog32 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:

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

請問，
EXP10 = ?
EXP11 = ?

EXP10: m = (v > 0x3U) << 1

EXP11: ret += (v > 0x1);

延伸問題:

1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
3. 研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog
4. 運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作

測驗八

考慮以下 C++ 二元搜尋樹的程式:

typedef struct tnode *tree;                   
struct tnode {
    int data;   
    tnode *left;
    tnode *right;
    tnode(int d)
    {       
        data = d;
        left = right = 0;
    }           
};

void remove_data(tree &t, int d)
{
    tnode *p = t;
    tnode *q;
    while (p != 0 && p->data != d) {
        if (d < p->data) {
            q = p;
            p = p->left;
        } else {
            q = p;
            p = p->right;
        }
    }
    if (p != 0) {
        if (p->left == 0)
            if (p == t)
                t = p->right;
            else if (p == q->left)
                q->left = p->right;
            else
                q->right = p->right;
        else if (p->right == 0)
            if (p == t)
                t = p->left;
            else if (p == q->left)
                q->left = p->left;
            else
                q->right = p->left;
        else {
            tnode *r = p->right;
            while (r->left) {
                q = r;
                r = r->left;
            }
            p->data = r->data;
            if (r == p->right)
                p->right = r->right;
            else
                q->left = r->right;
            p = r;
        }
        delete p;
    }
}

函式 remove_data 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 remove_data 過於冗長，於是我們可善用 indirect pointer 改寫為以下:

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

請問，
EXP12 = ?
EXP13 = ?
EXP14 = ?

首先我們看看這個題目，確定找到該點 p 的 data = d 之後，在 if-else裡主要有三種情況。對應於 if (!q->left) 、 else if (!q->right) 、 else 。

分別為 p 無左子點 、 p 無右子點 、 p 有兩個子點。
首先我們先把簡單的 EXP12 、 EXP13 填上。

EXP12: p = &(*p)->left;
EXP13: p = &(*p)->right;

(這裡目前在想改 *p 還是 p 比較好)

EXP14: r = &(*r)->left;

延伸問題:

1. 解釋上述程式碼運作原理
2. 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
3. 研讀 Static B-Trees，探討針對記憶體佈局 (memory layout) 的改進策略

測驗九

考慮以下進行記憶體地址對齊 (alignment) 的巨集:

/* 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))

作用是向上對齊 (roundup)。
請問，
MMM = ?
NNN = ?

這題的對齊可以先看第二題的概念。

(((x) + MAX_ALIGNMENT - 1 ) & ~(MAX_ALIGNMENT - 1)) //(((x) + MAX_ALIGNMENT - (x << 1) ) & ~(x | 3))

原來這題是將位置對齊 MAX_ALIGNMENT 的位置，我一直以為是根據 x 來決定對齊的位置，因此一直想不出來。假如是對齊 MAX_ALIGNMENT 就是將 最 LSB 的 4 個 bits 用反相 & 清為 0 。

延伸問題:

1. 解釋上述程式碼運作原理，並撰寫出對應 ROUND_DOWN 巨集
2. 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合

測驗十

考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:

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

注意: 當除數 (即 divisor) 為負值時，行為沒有定義。
參考執行結果:

DIVIDE_ROUND_CLOSEST(7, 3) = 2
DIVIDE_ROUND_CLOSEST(6, 3) = 2
DIVIDE_ROUND_CLOSEST(5, 3) = 2

請問，
RRR = ?
SSS = ?

RRR: __x;
SSS: -__x;

本來這樣寫就可以了，但是參考別人的想法，因為 c 語言會無條件捨去，所以我們要四捨五入時就要做補正了。 這裡的 (_d >> 1)/_d 之後會變 0.5 ，因此我們先加完再除的時候就等於補正 0.5 的數值了。

RRR: __x + (_d >> 1)
SSS: -__x - (_d >> 1)

延伸問題:

解釋上述程式碼運作原理
在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合

測驗十一

考慮以下計算整數開平方根的實作:

static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) {
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) {
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))
        num -= 1;
    return num;
} 

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        XXX;

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }

    return y;
}

i_sqrt 函式的作用等同於 floor(sqrt(x))

請問，

XXX = ?
YYY = ?
ZZZ = ?

XXX: b *= b;
YYY: x -= b;
ZZZ: m = m >> 1;

我們可以知道 fls() 是找到最少需要儲存的 bits 數(也就是 MSB 的位置)，因此初始 m 比 我們的 x 高一個bits，肯定大於 x 。

延伸問題:

1. 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
2. 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景