2024q1 Homework4 (quiz3+4)

contributed by < BooleanII >

第 3 週測驗題

測驗 1

版本一使用 log2 操作，可獲得小於等於輸入值的 2 的冪次數值 a ，並以此數值進行 Digit-by-digit calculation 獲得平方根。

int msb = (int) log2(N);
int a = 1 << msb;

而 a 其實可以透過第 2 週測驗的測驗 3 ，使用 ffs (find first bit) 找尋 N 第一個 set (設定為 1) 的位元，而版本 2 即為以找到 ffs 的方式進行實作。

待確認問題

1. 為何 log2 除了需要引入 math.h 檔外，在編譯時還需要連結 math library ？

測驗 2

測驗 3

由於向左或向右位移一個位元等同於將該數值乘或除以 2 ，故 2 的冪次可以透過將 1 左移進行實現。因此，以 2 為底的對數的整數項，可以透過找到該數的 ffs 獲得，版本一的實作輸入數值進行右移直到找該數值的 ffs 後停止。版本一的實作對於輸入數值小於等於 0 時，則輸出 -1 進行例外處理。

版本二為加快運算速度，以二元搜尋 (binary search) 的方式找出 ffs ，當數值大等於 2 的 16 次冪 (0x10000) 時，可以直接一口氣像右位移 16 個位元；而當數值大於等於 2 的 8 次冪 (0x100)時，則可以一口氣向右位移 8 個位元。

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 0x10000) {
        result += 16;
        i >>= 16;
    }
    while (i >= 0x100) {
        result += 8;
        i >>= 8;
    }
    while (i >= 0x10) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

__builtin_clz 為 gcc 內建函式，可回傳無號整數 (unsigned int) 中自 MSB 開始到第一個 1 的 0 個數，以 32 bit 系統為例，當輸入為 2 時輸出為 31 、輸入為 16 時輸出為 27 。透過使用此函式可獲得版本三的實作，將 31 減去 __builtin_clz 結果即可得到 ffs 的位置。

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v));
}

故測 3 答案如下：

1. AAAA = 0x10000
2. BBBB = 0x100
3. CCCC = 0x10
4. DDDD = v

測驗 3 延伸問題

在 Linux 核心原始程式碼找出 log2 的相關程式碼 (或類似的形式)，並解說應用案例

在 /usr/src 路徑下搜尋 log2 關鍵字獲得非常可觀的搜尋結果，為縮小範圍改以本次測驗的內容 ilog2 搜尋，並在結果中看到 hashtable.h 定義的 HASH_BITS 巨集 (macro) 有使用。

#define HASH_SIZE(name) (ARRAY_SIZE(name))
#define HASH_BITS(name) ilog2(HASH_SIZE(name))

該巨集涉及到的 ARRAY_SIZE 巨集定義於 kernel.h 檔中：

/**
 * ARRAY_SIZE - get the number of elements in array @arr
 * @arr: array to be sized
 */
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))

__must_be_array 巨集定義於 compiler.h 檔中：

/* &a[0] degrades to a pointer: a different type from an array */
#define __must_be_array(a)	BUILD_BUG_ON_ZERO(__same_type((a), &(a)[0]))

BUILD_BUG_ON_ZERO 巨集定義於 build_bug.h 檔中：

#ifdef __CHECKER__
#define BUILD_BUG_ON_ZERO(e) (0)
#else /* __CHECKER__ */
/*
 * Force a compilation error if condition is true, but also produce a
 * result (of value 0 and type int), so the expression can be used
 * e.g. in a structure initializer (or where-ever else comma expressions
 * aren't permitted).
 */
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
#endif /* __CHECKER__ */

__same_type 巨集定義於 compiler_types.h 檔中：

/* Are two types/vars the same type (ignoring qualifiers)? */
#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))

__same_type 巨集使用 gcc 提供的 built-in 函式 __builtin_types_compatible_p 進行實作。 __builtin_types_compatible_p 用於比較兩個輸入參數的型態是否相同，相同則回傳 １　、不同則回傳　０　。需注意此巨集會忽略如 const 、 volatile 等 top level qualifier ，例如 int 與 const int 會被視為相同。

當 BUILD_BUG_ON_ZERO 巨集輸入為非 0 時，程式碼會因為於 struct （結構體）中宣告 -1 的 bit field ，而在編譯階段發生錯誤；反之輸入為 0 時則則因 bit field 長度為 0 而輸出 0 。透過上述機制使 __must_be_array 輸入為 pointer （指標）時，會在編譯時期就發生錯誤，避免後續獲得錯誤的陣列長度計算結果。

Array-size macro that rejects pointers

測驗 4

測驗 5

第 4 週測驗題

測驗 1

測驗 2

測驗 3