Try   HackMD

2022q1 Homework3 (quiz3)

contributed by < freshLiver >

第一題 - GENMASK (LEFT, RIGHT)

// 產生一個第 `l` 到第 `h` 個位元皆為 1、而其他位元則為 0 的數值
#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

這段程式碼是利用對 ~0UL（64 個 1）進行位移來將重疊部份（第 l 到 h 位元）以外的部份皆設為 0，而需要設為 0 的區段有：

  • 前 63 - h 個位元：因此 LEFT 應為 (63 - h)。
  • 後 l 個位元：由於已經先右移 l 位元了，所以要再左移 l 位元才能使最低 l 位元皆為 0，因此 RIGHT 應為 l。

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

先備知識

在看 Linux 核心中 GENMASK 的實作之前，要先來了解相關巨集以及 GNU C Extensions 的用途以及原理：

巨集 - UL
// include/uapi/linux/const.h
#define __AC(X,Y)      (X##Y)
#define _AC(X,Y)       __AC(X,Y)
#define _UL(x)         (_AC(x, UL))

// include/vdso/const.h
#define UL(x)          (_UL(x))

UL 是一個定義在 include/vdso/const.h 中的巨集，展開後會變成 (((x##Y)))，而其中的 ## token concatenation，可以在前處理階段時將 x、y 兩個 token 合併，因此這個巨集展該後相當於在 x 後加上一個 UL 後綴。

接著根據 n1570 的 6.4.4.1 Integer constants 可以知道 U 以及 L 分別代表了 unsigned-suffix 以及 long-suffix。而在 6.4.4.1 的第 2 項則說明了這個後綴是用來指定一整數常數的型別：

  1. An integer constant begins with a digit, but has no period or exponent part. It may have a prefix that specifies its base and a suffix that specifies its type.

因此可以知道這個巨集是用來表示整數常數 x 為 64 位元無號整數（LP64）。

巨集 - BUILD_BUG_ON_ZERO
// include/linux/build_bug.h
#ifdef __CHECKER__
#define BUILD_BUG_ON_ZERO(e) (0)
#else 
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
#endif

TODO : __CHECKER__ 在哪被定義

這是一個定義在 include/linux/build_bug.h 的巨集，可以看到當 __CHECKER__ 有被定義時，這個巨集會展開成：

((int)(sizeof(struct { int:(-!!(e)); })))

這邊使用了 Bit-Fields 的技巧，

  1. The expression that specifies the width of a bit-field shall be an integer constant expression with a nonnegative value that does not exceed the width of an object of the type that would be specified were the colon and expression omitted.
    122)     If the value is zero, the declaration shall have no declarator.

而根據 6.5.3.3 Unary arithmetic operators 的第 5 項中則有明確規範一元運算子 ! 的結果只會是 0 或 1：

  1. The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int. The expression !E is equivalent to (0==E).

因此當 e 為非 0 時，這個 bit-field 的 width 會是 -1，但由於 bit-field 的 width 必須為非負整數，所以會產生錯誤造成編譯失敗；相對的，當 __CHECKER__ 沒定義或是 e 為 0 時則不會出現錯誤，而是會展開成常數 0 或是一個回傳 0 的表示式。

在 bit-field 一文中則有更詳細的說明。

Extension - __builtin_choose_expr(const_exp, expr1, expr2)

__builtin_choose_expr 是 GCC 的內建函式，根據文件中對這個函式的說明：

You can use the built-in function __builtin_choose_expr to evaluate code depending on the value of a constant expression. This built-in function returns exp1 if const_exp, which is an integer constant expression, is nonzero. Otherwise it returns exp2.

This built-in function is analogous to the ‘? :’ operator in C, except that the expression returned has its type unaltered by promotion rules. Also, the built-in function does not evaluate the expression that is not chosen. For example, if const_exp evaluates to true, exp2 is not evaluated even if it has side effects.

This built-in function can return an lvalue if the chosen argument is an lvalue.

If exp1 is returned, the return type is the same as exp1’s type. Similarly, if exp2 is returned, its return type is the same as exp2.

可以知道，這個內建函式跟三元運算子 ?:; 相似，都是根據條件是否成立來決定要進行的操作，但 __builtin_choose_expr 這個函式要求條件 const_expr 必須為常數，否則會造成編譯失敗。

TODO : 與 ?:; 的用途、優缺點比較

巨集 - __is_constexpr
#define __is_constexpr(x) \
	(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))

這個巨集被定義在 include/linux/const.h 中，可以用來檢查 x 是否能夠在編譯時期被視為常數。

TODO : 原理

若是 x 能夠在編譯階段被視為常數的話，這個巨集就會回傳 1，否則則會回傳 0。

GENMASK 實作

在 include/linux/bits.h 中有定義 GENMASK 相關的巨集：

// include/linux/bits.h
#define __GENMASK(h, l) \
	(((~UL(0)) - (UL(1) << (l)) + 1) & \
	 (~UL(0) >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK(h, l) \
	(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))

而 GENMASK 又會根據 __ASSEMBLY__ 的定義與否展開成不同的內容：

#if !defined(__ASSEMBLY__)
#include <linux/build_bug.h>
#define GENMASK_INPUT_CHECK(h, l) \
	(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
		__is_constexpr((l) > (h)), (l) > (h), 0)))
#else
/*
 * BUILD_BUG_ON_ZERO is not available in h files included from asm files,
 * disable the input check if that is the case.
 */
#define GENMASK_INPUT_CHECK(h, l) 0
#endif

可以看到若是 __ASSEMBLY__ 有被定義的話，就會展開成

#define GENMASK_INPUT_CHECK(h, l) \
	(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
		__is_constexpr((l) > (h)), (l) > (h), 0)))

而從前面的說明可以知道這段可以應該 2 種情況討論：

  • 若 (l) > (h) 能夠在編譯時期被確認是成立：
    1. __is_constexpr 在編譯時期被相當於 1
    2. __builtin_choose_expr 會選擇 (l) > (h) 的表示式
    3. 由於 (l) > (h) 成立，所以 BUILD_BUG_ON_ZERO 會產生錯誤、造成編譯失敗
  • 若 (l) > (h) 在編譯時期被確認是不成立，或無法確認是否成立：
    1. __is_constexpr 在編譯時期被相當於 0
    2. __builtin_choose_expr 會選擇 0 的表示式
    3. 由於 0 代表不成立，所以 BUILD_BUG_ON_ZERO 不會產生錯誤

因此可以知道這段複雜的巨集用意是在避免使用常數作為 GENMASK 巨集的參數時誤將傳入數值比 h 大的 l。

在 GCC 內建函式中有類似的函式 __builtin_constant_p(exp) 能夠作到與 __is_constexpr 相似的檢查，而原先的 GENMASK 巨集也是依賴這個內建函式進行檢查，但在 2018 年 3 月時被反應 __builtin_constant_p 在編譯時可能無法在正確的時間點檢查 exp，因此會造成 __builtin_choose_expr 的 const_expr 部份被認為是非常數而導致編譯失敗。直到在 2021 年 3 月時才改用 __is_constexpr 來取代 __builtin_constant_p 進行判斷。

而在檢查完 h、l 之後（或因 __ASSEMBLY__ 未定義而不進行檢查），就會接著產生 mask 的部份：

#define __GENMASK(H, L) \
	(((~UL(0)) - (UL(1) << (L)) + 1) & \
	 (~UL(0) >> (BITS_PER_LONG - 1 - (H))))

因為 1 與 l 的字型非常相似，所以為了愛護眼睛，我將巨集的 h 以及 l 改用大寫字母 H 以及 L 替代。

可以看到這個巨集一樣是對 64 位元的無號整數 0 取一補數來產生 64 個 1 進行位移，而這邊將這個巨集分成兩部份討論：

  • ((~UL(0)) - (UL(1) << (L)) + 1) 的部份：
    • (~UL(0))：產生 64 個 1
    • - (UL(1) << (L))：將第 L 個位元值設成 0
    • + 1：使用 + 1 進位的特性，將最低位的 0（也就是第 L 個位元）設成 1，而其它更低的位元（即第 0 至 L-1 位元）則會因進位被設成 0
    • 到這邊可以產生第 L-1 ~ 0 位元皆為 0 的 mask
  • (~UL(0) >> (BITS_PER_LONG - 1 - (H))) 的部份：
    • (~UL(0)：產生 64 個 1
    • (BITS_PER_LONG - 1 - (H))：由於位元的編號是從 0 開始，所以最高位應為 63（即 BITS_PER_LONG - 1），而 - (H) 則是找出應要右移的位數
    • >> (BITS_PER_LONG - 1 - (H))：右移讓最高的 63 - (H) 個位元為 0
    • 到這邊可以產生第 63 ~ H+1 位元皆為 0 的 mask

最後再將兩個 mask 進行 AND 運算即可產生第 H ~ L 位元皆為 1 的 mask。

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

第二題 - ALIGN_DOWN (EXP1)

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

這段程式碼是要將一地址 v 看作是結構體 foo 的起始位置，若地址 v 沒有以 4 位元組進行對齊的話，則需要將地址向下對齊，因此 EXP1 要先捨去地址的後 2 個位元，然後再轉型成結構體 foo 的指標，即 EXP1 應為 (struct foo *)(v & ~3)。

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

在第九題的延伸問題中一併討論。

第三題 - LeetCode 190. Reverse Bits (EXP2, EXP3)









#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);        // 以 4 位元為單位，兩段互換
    x = ((x & 0xCC) >> 2) | (EXP2); // 以 2 位元為單位，0,1 2,3 段兩兩互換
    x = ((x & 0xAA) >> 1) | (EXP3); // 以 1 位元為單位，0,1 2,3 4,5 6,7 段兩兩互換
    return x;
}

將

n 個位元以不同單位大小分割成偶數段，每次將奇數部份以及偶數部份透過位移以及 bitwise-or 互換，而因為 0xCC 與 0xAA 分別代表 0b11001100 與 0x10101010，即分別為單位大小為 2 位元及 1 位元的偶數段部份，所以 EXP2 與 EXP3 應為對應單位大小的奇數段部份。因此 EXP2 應為 0x33 (0b00110011)，而 EXP3 則應為 0x55 (0b01010101)

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

在 include/linux/bitrev.h 中包含了 1, 2, 4 位元組反轉的巨集實作，可以看到大致上分成 3 種實作方式：

  1. bitwise 反轉（常數）

    當要反轉的值屬於常數時，則會直接使用與測驗題相似的方式，應該是為了讓編譯器能夠將常數運算直接最佳化掉。

  2. 查表（非常數且無硬體指令）

    在 lib/bitrev.c 中有透過陣列 byte_rev_table 列舉了 8 位元對應的反轉結果，因此當 CONFIG_HAVE_ARCH_BITREVERSE 沒有被定義時，可以不用以 4, 2, 1 位元作為單位大小進行反轉，直接透過查表找到該位元組對應的反轉結果即可。

  3. 反轉指令（非常數但有硬體指令）

    在某些架構的指令集中可能有能夠反轉位元的指令，像是 ARM 的 RBIT 指令 就能夠直接反轉一個 32 位元的資料。因此在 CONFIG_HAVE_ARCH_BITREVERSE 有被定義時就能夠直接使用指令進行更有效率的反轉操作。

第四題 - foreach (EXP4, EXP5)

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

兩個 for each 巨集的實作概念都差不多，使用了 Variadic Macro 進行陣列宣告，並透過 for 迴圈以及 , 運算子：

在規格書中的 6.5.17 Comma operator 中關於 , 這個運算子的說明：

  1. Syntax :
​​ expression:
​​     assignment-expression
​​     expression , assignment-expression
  1. The left operand of a comma operator is evaluated as a void expression; there is a sequence point between its evaluation and that of the right operand. Then the right operand is evaluated; the result has its type and value.
  2. EXAMPLE As indicated by the syntax, the comma operator (as described in this subclause) cannot appear in contexts where a comma is used to separate items in a list (such as arguments to functions or lists of initializers). On the other hand, it can be used within a parenthesized expression or within the second expression of a conditional operator in such contexts. In the function call f(a, (t=3, t+2), c) the function has three arguments, the second of which has the value 5.

因此在 for 迴圈的初始化部份會先執行 , 左側，也就是先將陣列的第一個元素賦值給變數 i，最後才會將 , 右側的 0，也就是陣列的初始 index 賦值給 _foreach_i。

除了初始化用來儲存陣列的變數 i 以及陣列 index 的變數 _foreach_i 之外，每次迴圈結束還需要增加 _foreach_i 並將 i 移動到下一個元素，因此 _foreach_i 可以直接透過 ++_foreach_i 或 _foreach_i++ 增加，但 i 由於並不是指標，所以必須重新初始化陣列，並將下一個元素透過 _foreach_i 賦值給 i，因此 EXP4 與 EXP5 皆應為 ++_foreach_i 才能在每次迭代結束時將正確的元素重新賦值給 i。

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

透過 $ grep -rP --include="*.[ch]" "\\[\\].*__VA_ARGS__.*" 尋找相關用法大多是用來初始化陣列或是檢查巨集參數的數量，其中與這題比較相近的是：

// drivers/gpu/drm/i915/i915_reg.h
/*
 * Given the arbitrary numbers in varargs, pick the 0-based __index'th number.
 *
 * Always prefer _PICK_EVEN() over this if the numbers are evenly spaced.
 */
#define _PICK(__index, ...) (((const u32 []){ __VA_ARGS__ })[__index])

除了透過單純宣告成一個陣列之外，還能透過指定 index 來取得目標參數。

第五題 - 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;
}

指出可改進部份並實作

無乘法、無迴圈以外的 branch

int divide(int dividend, int divisor)
{
    uint32_t sign = 0;

    int dvd_mask = dividend >> 31;
    sign ^= dvd_mask & 0xFFFFFFFF;
    // explicitly cast to unsigned to avoid overflow
    uint32_t dvd = (uint32_t) (dividend ^ dvd_mask) - dvd_mask;

    int dvs_mask = divisor >> 31;
    sign ^= dvs_mask & 0xFFFFFFFF;
    // explicitly cast to unsigned to avoid overflow
    uint32_t dvs = (uint32_t) (divisor ^ dvs_mask) - dvs_mask;

    uint8_t shift = 0;
    while (dvd > (dvs << shift))
        ++shift;

    uint32_t res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            --shift;
        // 1 should be unsigned to avoid overflow (1 << 31)
        res |= 1U << shift;
        dvd -= dvs << shift;
    }

    res |= -!!(res > 0x7FFFFFFFU && !sign) & 0x7FFFFFFFU;
    // explicitly cast to unsigned to avoid overflow
    res ^= (uint32_t)(res > 0x7FFFFFFFU && !sign) << 31;
    return (res ^ sign) - sign;
}

找出並討論 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;
}

指出可改進部份並實作

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

第七題 - ilog32

/**
 * @brief 對於一 32 位元無號整數 @v 最少需要幾位元才能儲存
 *
 * 儲存最少需要的位元數 = 最高位元 1 的位置 (32-clz)
 * 因此可以可以透過 BITMASK 將資料分成高位元以及低位元兩部份，並檢查最高位元的 1
 * 在哪部份：
 * - 若是不在高位元部份就縮小範圍再檢查一次。
 * - 若是在高位元部份的話就紀錄並移除低位元部份，然後縮小範圍再重新檢查一次。
 */
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;
}

以二元搜尋的概念找出最高位元的 1 的位置，從中間開始，每次都將檢查範圍縮小一半，當最高位 1 位於高位元部份時，則可以右移掉低位元部份，讓兩種狀況能以相同的形式繼續進行檢查。若是以這個邏輯實作的話，只要重複三行程式碼：


























    // 檢查最高位 1 是否在 16 - 31 位元
    int m = (v > 0xFFFFU) << 4;
    v >>= m;  // 若是的話 m 會變成 16，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;  // 相當於 ret += m，即用來紀錄最高位 1 的位置


    // 檢查最高位 1 是否在 或 8 - 31 位元
    m = (v > 0xFFU) << 3;
    v >>= m;  // 若是的話 m 為 8，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

    // 檢查最高位 1 是否在 或 4 - 31 位元
    m = (v > 0xFU) << 2;
    v >>= m;  // 若是的話 m 為 4，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

    // 檢查最高位 1 是否在 或 2 - 31 位元
    m = (v > 0x3U) << 1; /* EXP10 */
    v >>= m;  // 若是的話 m 為 2，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

    // 檢查最高位 1 是否在 或 1 - 31 位元
    m = (v > 0x1U) << 0;
    v >>= m;  // 若是的話 m 為 1，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

可以簡單的知道 EXP10 應為 (v > 0x3U) << 1，即用來檢查最高位元 1 是否在第 2 至 31 位元。

但這樣會因為每次都分成兩長度不為 0 的部份，所以最多只能檢查 31 個位元，造成當 v == 1 時會產生錯誤結果，因此最後還需要檢查 v 是否在第 0 個位元，即 v 是否為 0：

    ret += (v > 0);

這邊要注意的是，由於前面都是透過 | 設定 ret 的第 0 至第 5 位元來紀錄所需位元數，因此最後需要改用 +，才不會在某些情況（第 23 行條件成立時）產生錯誤結果。

在了解檢查機制之後，需要注意到在原程式碼的一開始宣告 int ret = v > 0; 時就已經先檢查 v > 0 的情況了，所以需要改用 + 的是第 23 至 25 行的部份：





    // 檢查最高位 1 是否在 或 1 - 31 位元
    m = (v > 0x1U) << 0;
    v >>= m;  // 若是的話 m 為 1，否則為 0 (代表能夠捨棄的位元數)
    ret += m;

而這邊又可以在進行簡化（左移 0 可以忽略、v 不須再右移、m 與 ret 的操作可以合併）：

    ret += (v > 0x1);

應此 EXP11 最精簡的表示法應為 ret += v > 1。

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

quiz4 的 ilog2 說明。

缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog

研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》

實作編譯時期 (compile-time) 的 ilog2 實作

運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧

第八題 - 二元搜尋樹 (C++)












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















































// native.cpp
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;
    }
}

使用 indirect pointer 改寫簡化：





























// improve.cpp
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;
}

以更精簡、高效且符合 C99 標準進行實作探討效率的提升

探討針對記憶體佈局 (memory layout) 的改進策略

研讀 Static B-Trees

第九題 - ALIGN_UP

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

與實作四捨五入的概念（加上 0.5 再捨去小數點部份）有點相似，直接對地址加上對齊大小（這段程式碼為 16 位元組對齊），接著再捨去地址的最低 4 位元，因此 ~(NNN) 應為除最低 4 位元皆為 1 的數，即 NNN 應為 MAX_ALIGNMENT - 1 (15)。

但是直接加上對齊大小會讓已對齊的地址也被向上對齊，因此要先讓原地址 x 減 1 才能確保已對齊的地址向上對齊後保持不變，所以 MMM 應為 1。

撰寫出對應 ROUND_DOWN 巨集

#define MAX_ALIGNMENT 16
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) ((x) & ~(MAX_ALIGNMENT - 1))

跟第二題的概念相同，直接捨棄地址最後的

log2(MAX_ALIGNMENT)−1 個位元。

找出並說明 Linux 核心中 round-up/round-down 的應用場合

md raid metadata

// driver/md/raid1.h
/*
 * each barrier unit size is 64MB fow now
 * note: it must be larger than RESYNC_DEPTH
 */
#define BARRIER_UNIT_SECTOR_BITS	17
#define BARRIER_UNIT_SECTOR_SIZE	(1<<17)

// driver/md/raid1.c
static sector_t align_to_barrier_unit_end(sector_t start_sector,
					  sector_t sectors)
{
	sector_t len;

	WARN_ON(sectors == 0);
	/*
	 * len is the number of sectors from start_sector to end of the
	 * barrier unit which start_sector belongs to.
	 */
	len = round_up(start_sector + 1, BARRIER_UNIT_SECTOR_SIZE) -
	      start_sector;

	if (len > sectors)
		len = sectors;

	return len;
}

第十題 - DIVIDE_ROUND_CLOSEST

#define DIVIDE_ROUND_CLOSEST(x, divisor)                          \
    ({                                                            \
        /* evaluate once */;                                      \
        typeof(x) __x = x;                                        \
        typeof(divisor) __d = divisor;                            \
        /* check unsigned or not */;                              \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 ||    \
         (((__x) > 0) == ((__d) > 0)))                            \
            ? ((7777 /* RRR */) / (__d))                          \
            : ((8888 /* SSS */) / (__d));                         \
    })

/**
 * True : SSS 皆可以用 "被除數 + 0.5 * 除數" 表示
 *  - TTT 兩數皆為無號
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 皆非 0 : divide by zero，不處理
 *
 *  - FTT 被除數為有號，除數為無號
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 除數必為 0 : divide by zero，不處理
 *
 *  - TFT 被除數為無號，除數為有號
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 被除數為 0，除數為負數 : 0 >= SSS > 除數
 *      3. 被除數為 0，除數為 0 : divide by zero，不處理
 *
 *  - FFT 兩數皆為有號數
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 皆為負數 : SSS = 被除數 - 0.5 * |除數|
 *      3. 被除數為 0，除數為負數 : 0 >= SSS > 除數
 *      4. 被除數為負數，除數為 0 : divide by zero，不處理
 *      5. 被除數為 0，除數為 0 : divide by zero，不處理
 *
 *  - FTF 被除數為無號，除數為有號，恰一數為非正數
 *      1. 被除數為 0，除數為正 : -除數 < SSS < 除數
 *      2. 被除數為正，除數為負 : SSS = 被除數 + 0.5 * |除數|
 *      3. 被除數為正，除數為 0 : divide by zero，不處理
 *
 *  - TFF 被除數為有號，除數為無號，恰一數為非正數
 *      1. 被除數為 0，除數為正 : -除數 < SSS < 除數
 *      1. 被除數為負，除數為正 : 
 *      1. 被除數為正，除數為 0 : divide by zero，不處理
 *
 *  - TTF 兩數皆為無號數，但恰有一數為非正數 (0)
 *      1. 被除數為 0，除數為正數 : -除數 < SSS < 除數
 *      2. 被除數為正數，除數為 0 : divide by zero，不處理
 *
 * 
 * False : RRR 皆可以用 "被除數 - 0.5 * 除數" 表示
 *  - FFF 兩數皆為有號型別，且恰有一數為非正數 :
 *      1. 被除數為正，除數為負 : RRR = 被除數 + 0.5 * |除數|
 *      2. 被除數為負，除數為正 : RRR = 被除數 - 0.5 * 除數
 *      3. 被除數為 0，除數為正 : -除數 < RRR < 除數
 *      4. 被除數為正，除數為 0 : divide by zero，不處理
 *
 */

找出並說明 Linux 核心中 div round-up/closest 的實作與使用情景

在 insmod 時，會使用到定義在 include/linux/module_decompress.c 中的 module_decompress，而其中又會使用到 DIV_ROUND_UP 來確保核心模組解壓縮後仍有足夠空間能儲存資訊。

第十一題 - Integer Square Root





























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

嘗試利用硬體的 clz/ctz 指令改寫

在 Linux 核心找出類似的巨集和程式碼，說明其應用場景

Last changed by 
 
freshLiver
0
444
Published on HackMD