2022q1 Homework3 (quiz3)

contributed by < Wallmountain >

測驗1

在 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) >> (63 - h)) & ((~0UL) >> (l) << (l)))

可將 GENMASK 簡單分成兩個流程:

1. 從第 h 個位元開始到最高位元都為 0 => (~0UL) >> (63 - h)
2. 從第 l - 1 個位元開始到最低位元都為 0 => (~0UL) >> (l) << (l)

並將以上兩條件取 & 就為 GENMASK 產生方式

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

#define GENMASK(h, l) \
	(((~0UL) << (l)) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

我們實作的程式碼的第二個條件使用了兩次位移，而 linux的實作則避免了兩次位移的操作

• 從第 l - 1 個位元開始到最低位元都為 0 => (~0UL) << (l)

舉出 Linux 核心原始程式碼中二處 GENMASK 巨集

1. drivers/clk/clk-multiplier.c 中出現以下程式碼

static unsigned long clk_multiplier_recalc_rate(struct clk_hw *hw,
						unsigned long parent_rate)
{
	struct clk_multiplier *mult = to_clk_multiplier(hw);
	unsigned long val;

	val = clk_readl(mult->reg) >> mult->shift;
	val &= GENMASK(mult->width - 1, 0);

	if (!val && mult->flags & CLK_MULTIPLIER_ZERO_BYPASS)
		val = 1;

	return parent_rate * val;
}

• 在程式碼中，利用 GENAMASK 產生從最低位元到第mult->width - 1 為1而剩下為0的值

2. drivers/clk/mediatek/clk-pll.c 中也是用一樣的方式

PLL 為 Phase-locked loop 的縮寫，是一種控制系統，最簡單的是由一個可變頻率振盪器和一個反饋迴路中的相位檢測器組成的電子電路，一般而言，模擬 pll 會包含四個部分，分別為相位頻率偵測器 (Phase Frequency Detector), 低通濾波器, 壓控振盪器, 反饋迴路(Feedback)。

• 相位頻率偵測器: 簡稱 PFD，可比較兩種輸入訊號的相位誤差及頻率誤差
• 低通濾波器 : 容許低頻訊號通過，減弱頻率高於截止頻率的訊號的通過，不同的濾波器對每個平率的訊號的減弱效果不同
• 壓控振盪器 : 以電壓輸入來控制振盪頻率，振盪的頻率或重覆的比例會隨著直流電壓的不同而改變
• 反饋迴路 : 將壓控振盪器輸出的信號送回至鑒頻鑒相器，壓控振盪器輸出信號通常大於參考信號的頻率，因此需要分頻器的幫助

接著，這段程式碼中使用到 GENMASK，列出的程式碼擔任分頻器的角色

static unsigned long mtk_pll_recalc_rate(struct clk_hw *hw,
		unsigned long parent_rate)
{
	struct mtk_clk_pll *pll = to_mtk_clk_pll(hw);
	u32 postdiv;
	u32 pcw;

	postdiv = (readl(pll->pd_addr) >> pll->data->pd_shift) & POSTDIV_MASK;
	postdiv = 1 << postdiv;

	pcw = readl(pll->pcw_addr) >> pll->data->pcw_shift;
	pcw &= GENMASK(pll->data->pcwbits - 1, 0);

	return __mtk_pll_recalc_rate(pll, parent_rate, pcw, postdiv);
}

static unsigned long __mtk_pll_recalc_rate(struct mtk_clk_pll *pll, u32 fin,
		u32 pcw, int postdiv)
{
	int pcwbits = pll->data->pcwbits;
	int pcwfbits;
	u64 vco;
	u8 c = 0;

	/* The fractional part of the PLL divider. */
	pcwfbits = pcwbits > INTEGER_BITS ? pcwbits - INTEGER_BITS : 0;

	vco = (u64)fin * pcw;

	if (pcwfbits && (vco & GENMASK(pcwfbits - 1, 0)))
		c = 1;

	vco >>= pcwfbits;

	if (c)
		vco++;

	return ((unsigned long)vco + postdiv - 1) / postdiv;
}

在裡面的註解表示最多有 7 個位元為整數的部分，而剩餘的部分則為小數的部分

• 在 12 行使用了第一次的 GENMASK，用以確保 pcw 的範圍
• 在 26 行則是確認裡面是否含有小數的部分
• 在 30 行的意義為若有小數的部分且小數的部分不為0，就將 c 變數設為1
• 在 33 行去除小數的部分
• 然後若 c 為 1，則加 1，代表將剛剛小數的部分進位
• 最後回傳分頻後的結果

在程式碼的部分，主要是將小數的部分去除，若有小樹則將其無條件進位到個位數，並且在最後回傳分頻後的結果

---

測驗2

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

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

• 對4個位元作對齊，利用 ~3 最後兩個位元為0的特點進行對齊，並以 (struct foo *) 的 type 將地址指向對齊過後的位址

測驗3

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

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

• 利用 Divide and conquer 拆分問題的技巧，持續將要互相交換的 bit 寬度縮減，每次都將寬度變成一半，直到寬度剩下1位元

32 位元無號整數版本

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 16);
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
    return n;
}

測驗4

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

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

__VA_ARGS__ 為一個 variadic macro，支援不同數量的參數，利用 "..." 來表示一個或多個參數， 而 regular macro arguments 都須放在 "..." 前面

1. 在 C99 和 C++11 都須至少傳送一個參數，而剩餘的編譯器幾乎沒有這個規定

• 利用 __VA_OPT__ 去除了這個限制

2. GNU CPP 有另一個延伸，利用 "##" 去除 regular macro arguments 和 variadic macro 之間的逗號，解決前置處理器延展之後的錯誤

• ​​  #define eprintf(format, ...) fprintf (stderr, format, __VA_ARGS__)
  ​​  
  ​​  eprintf("success!\n", );
  ​​   → fprintf(stderr, "success!\n", );
  ​​   
  ​​  #define eprintf(format, ...) fprintf (stderr, format, ##__VA_ARGS__)
  ​​  
  ​​  eprintf ("success!\n")
  ​​   → fprintf(stderr, "success!\n");
  

以上 foreach 的用途為利用 __VA_ARGS__ 將後面傳入的參數變成 array，並用 for 迴圈存取裡面的內容

foreach_int的 type 為 array of unsigned int，故要在 array 的最後加上0，判斷 array 的結尾
foreach_ptr的 type 為 array of char *，故要在 array 的最後加上 NULL，判斷 array 的結尾

測驗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 > (dvs << shift))
        shift++;

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

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

一開始，將兩個傳入的參數賦值給型態為 unsigned int 的變數，是因為最小的負值轉成正的會溢出
利用二進位的特點進行除法，確認除數要向左位移幾次能到不超過被除數的最大數，此時被除數減去位移過後的除數，並記錄商數，持續這個步驟，直到被除數不大於除數

改善 code

初始程式碼用 while 迴圈來尋找除數要位移幾次才能比被除數大，而過程中進行了多次比較，而將其改善程利用 __builtin_clz 來找到兩個相差幾次位移，但還是需要一次比較來確定在進行這次位移之後，除數是否會大於被除數

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

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

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

改善方向可以盡力去尋找把 branch 去掉的可能性

測驗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 p1 == pn->p1;
    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;
                    list_add(&pn->link, &heads[hash]);
                }
            }
        }
    }

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

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

以這個函式可以涵蓋的範圍為32個位元，每次去搜索當前剩餘範圍的一半，來加速一個一個搜索的速度

• 第一次，搜索16個位元 -> v > 0xFFFFU，若成立則帶只需再去搜索最大16個位元，反之則只需要搜索最小16個位元。
• 第二次，搜索8個位元 -> v > 0xFFU，若成立則帶只需再去搜索當前範圍最大8個位元，反之則只需要搜索當前範圍最小8個位元。
• 以此類推

測驗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)
            p = &(*p)->left;
        else
            p = &(*p)->right;
    }
    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;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

利用 indirect pointer 可以減少去判斷當前 node 狀態的分支。

測驗9

考慮以下進行記憶體地址對齊 (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 - 1) & ~(MAX_ALIGNMENT - 1))

測驗10

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

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

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

以題目而言，就是進行四捨五入，首先判斷被除數與除數是否同號

• 同號 -> 被除數加上除數的一半再去除除數，以此若原本除完的餘數超過除數的一半便會進位
• 不同號 -> 被除數減去除數的一半再去除除數，以此若原本除完的餘數超過除數的一半便會進位

測驗11

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

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;
        y >>= 1;

        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }

    return y;
}