2022q1 Homework3 (quiz3)

contributed by < Kevin-Shih >

測驗 1

題目

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

GENMASK(6, 4) 產生 01110000₂
GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:

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

請補完，使其行為符合預期。

運作原理與解題

AND 的左邊可以看出是要透過 ~0UL 右移產生低位的 h bits 均為 1 的 unsigned long，而右側則是以左移產生低位 l bits 均為 0 的 unsigned long 接著就可以用 AND 運算得到 h 至 l 之間的 bits 均為 1 的 bitmask。

因此 LEFT 應為 63 - h，以產生低位 h bits 均為 1 的 unsigned long， RIGHT 應為 l 以產生低位 l bits 均為 0 的 unsigned long。

由於左移超過變數長度時，其結果在 c 屬於未定義行為，因此先左移 l bits 再右移 l bits 以避免此情形發生。

TODO

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

比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量

舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 include/linux/bitfield.h 的應用案例

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

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

請補完，使其行為符合預期。

運作原理與解題

由於 fd 結構體的第一個成員是指向 struct foo 結構體的指標，因此 EXP1 肯定要將 unsigned long 型態的 v casting 成指向 struct foo 型態的指標，即 EXP1 前面一定包含 (struct foo *)。

接著由於要作 4 byte 的 align down 因此代表 2¹, 2⁰ 的最低位 2 bits 應設為 0 (低位的 log₂(4) 個 bits 設為 0)，而這可以透過 AND 一個最低 2 位為 0 的 bitmask 達成，最簡潔的寫法是透過取 3 的 1 補數達成。

因此 EXP1 = (struct foo *)(v & ~3)

TODO

在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

測驗 3

題目

考慮以下程式碼，能將輸入的 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;
}

請補完，使其行為符合預期。

運作原理與解題

進行 rev8 前的一個 uint8_t 示意圖

為求方便辨識原本的 0 到 7 bit 分別以 0 到 7 標注

#2 將高位 4 bits 與低位 4 bits 對調後

#3 左半邊可以看出是將 4 bits 內的高位 2 bits 調至低位 2 bits，因此不難猜出 EXP2 是將 4 bits 內的低位 2 bits 調至高位 2 bits，調換後的示意圖如下

#4 的左半邊當然就是將 2 bits 內的高位 bit 調至低位 bit，因此 EXP3 是將 2 bits 內的低位 bit 調至高位 bit，調換後的示意圖如下

由上面的步驟得出答案為

EXP2 = (x & 0x33) << 2
EXP3 = (x & 0x55) << 1

0x33 = 0b00110011, 0x55 = 0b01010101

TODO

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 4

題目

延伸〈你所不知道的 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__})))

請補完，使其行為符合預期。

運作原理與解題

從程式碼可以看出不論是 foreach_int, foreach_ptr 中的 _foreach_i 都是用來標示讀到第幾個 __VA_ARGS__ 的，因此每次迴圈 foreach_int 應加 1，而由於每次迴圈的更新要對 i 賦值，使其值等於下個 __VA_ARGS__ 中的值，因此 EXP4, EXP5 = ++_foreach_i，而非 _foreach_i++。 (先更新 foreach_int 再對 i 賦值)

TODO

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 5

題目

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

請補完，使其行為符合預期。

運作原理與解題

#5 ~ #15 用於處理當除數或被除數有負值的時候將其轉為正值後存入對應的 unsigned int，並將其正負號紀錄於 signal 變數，方便後續運算。

#18 則是當被除數大於除數乘上 2^shift 時，代表商的最高位的 1 (first set bit) 至少在第 shift bit。就像十進位除法 900 除 10 我們會移到百位數後發現 9 < 10 最後從十位數開始寫商，而更大的位數則留下 0。

實際上跳出迴圈時 shift 會比商的 first set bit 的 index 多 1 但會在後續的 while loop handle

因此 EXP6 = dvs << shift

#22 開始的 while loop 是整個除法的主體，內層的 while loop 就是在處理先前比喻的 9 < 10 的情形下商會退 1 位再繼續寫若退 1 位後還是被除數還是小於位移後的除數就退到不小於為止。當被除數不小於位移後的除數時就將 1 紀錄到 res 中對應的 bit，並將被除數減去位移後的除數的值，因此 EXP7 = dvd -= dvs << shift，而 while loop 會進行到剩下的 dvd 小於 dvs 為止。

最後將 res 乘上先前紀錄的正負號 signal 即為答案。

TODO

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

指出上述程式碼可改進之處，並予以實作

在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論

測驗 6

題目

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

請補完，使其行為符合預期。

運作原理與解題

TODO

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

指出上述程式碼可改進之處，並予以實作

擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行

測驗 7

題目

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

請補完，使其行為符合預期。

運作原理與解題

#3 當 v 是非零的值就至少需要 1 bit 紀錄，故 ret = v > 0

#4 ~ #6 當 v 的 first set 在高位的 16 bits 中， v 會右移 16 bits 並在剩下的 16 bits 繼續找 first set ， ret 則加上 16。若不是的話， m 會為 0 不影響後續步驟。 (會變成找低位的 16 bits 中使否有 first set)

#7 ~ #9 則是找在剩下的 16 bits 中 v 的 first set 是否在較高的 8 bits 中，若有 v 會再右移 8 bits 並在剩下的 8 bits 繼續找 first set ， ret 則加上 8。

後面依此類推，EXP10 是在最後 4 bits 中找 v 的 first set 是否在較高的 2 bits 中，因此 EXP10 = (v > 3) << 1。 EXP11 是在最後 2 bits 中找 v 的 first set 是在較高的 bit 中或是較低的那個，若是在較高的就將 ret += 1 若不是就不用加，因此 EXP11 = ret += v > 1。

EXP11 已經是最後一步了，所以直接改 ret 就好，不須再對 v 做位移或先紀錄到 m 。

TODO

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

在 Linux 核心原始程式碼找出類似實作並解說其應用場景

研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`

運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作

測驗 8

題目

考慮以下 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;
}

請補完，使其行為符合預期。

運作原理與解題

前面的 while loop 是在找要刪除的 node 依據二元搜尋樹的特性當要刪除的 node d 小於當前的 node 的 data，應向 left child 繼續搜尋，大於時則向 right child 搜尋。因此 EXP12 = p = &(*p)->left, EXP13 = p = &(*p)->right。

將 indirect pointer p 指向 *p 的 left 或 right 所在的記憶體位置

當要移除的 node 存在時 *p 會指向該 node，若否則 *p 會等於 null，而 p 則是指向該 node 的 parent 的 left 或 right 所在的記憶體位置。因此接下來只須將 *p 指向接替 node d 的 node 就完成 remove 了。

沒有左子樹或右子樹時

if (!q->left)
    *p = q->right;
else if (!q->right)
    *p = q->left;

當被移除的 node 沒有左子樹時直接以右子樹取代該 node。反之若沒有右子樹時直接以左子樹取代該 node。

左右子樹都存在時

tnode **r = &q->right;
while ((*r)->left)
    r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;

這邊是從右子樹中找最小的 node 取代要移除的 node。先以 r 指向要移除的 node 的 right，當該 node 有左子葉時 r 就指向 (*r)->left 所在的記憶體位置，一路找到沒有左子葉時就是右子樹中最小的 node。接著將這個 node 的 data 複製到要刪除的 node 中取代要被刪除的值，並將 q 指向該 node，並將 *r 指向 q 的右子樹。因此 EXP14 = &(*r)->left。

最後刪除 q 即可。

TODO

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

2022q1 Homework3 (quiz3)

測驗 1

運作原理與解題

比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量

舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

測驗 2

運作原理與解題

在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

測驗 3

運作原理與解題

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 4

運作原理與解題

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 5

運作原理與解題

指出上述程式碼可改進之處，並予以實作

在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論

測驗 6

運作原理與解題

指出上述程式碼可改進之處，並予以實作

擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行

測驗 7

運作原理與解題

在 Linux 核心原始程式碼找出類似實作並解說其應用場景

研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog

運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作

測驗 8

運作原理與解題

以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升

研讀 Static B-Trees，探討針對記憶體佈局 (memory layout) 的改進策略

Read more

2022q1 Homework1 (lab0)

2022q1 Homework5 (quiz6)

2022q1 Homework5 (quiz8)

2022q1 Homework5 (quiz5)

比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量

舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 include/linux/bitfield.h 的應用案例

研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`

運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作