# 2024q1 Homework4 (quiz3+4)
> contributed by <`brian049`>

## [Quiz 3](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗三
在測驗三當中針對 ilog 有三種版本，第一種版本透過不斷向右位移二進位位元來計算以 2 為底的對數。

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

第二種版本與第一種版本相似，但是是透過比較較大數字開始，一步一步將二進位位元向右位移到 0。

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

相對於第一種方式，第二種方式較為快速，我透過 Linux shell command `time` 指令來計算執行時間。

針對兩種方式我透過用兩種測資，一個測資為 65536，另一個測資為 87654321。

$ time ./v1
The logarithm base 2 of 65536 is: 16

real    0m0.006s
user    0m0.002s
sys     0m0.004s

$ time ./v2
ilog2 of 65536 is 16

real    0m0.008s
user    0m0.001s
sys     0m0.007s

$ time ./v1
The logarithm base 2 of 87654321 is: 26

real    0m0.027s
user    0m0.009s
sys     0m0.018s

$ time ./v2
ilog2 of 87654321 is 26

real    0m0.007s
user    0m0.001s
sys     0m0.006s

經過測試發現，若是測資較小，執行時間較無差異，但是若是測資較大，則執行時間差異較大。

第三種方式是透過呼叫 `__builtin_clz` 巨集來計算在二進位當中最高位元為 1 的位置，來得到以 2 為底的對數。

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

### 測驗三延伸問題
在 [linux/log2.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/log2.h) 當中有 ilog2 巨集的定義。

其實作的方法是暴力法（Brute force) 從 63 位元開始比對，若是向左位移 63 位元得到 1 時則是 2 的 63 次方，以此類推直到比對到第 2 位元。

/**
 * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
 * @n - parameter
 *
 * constant-capable log of base 2 calculation
 * - this can be used to initialise global variables from constant data, hence
 *   the massive ternary operator construction
 *
 * selects the appropriately-sized optimised version depending on sizeof(n)
 */
#define ilog2(n)				\
(						\
	__builtin_constant_p(n) ? (		\
		(n) < 2 ? 0 :			\
		(n) & (1ULL << 63) ? 63 :	\
		(n) & (1ULL << 62) ? 62 :	\
		...
		(n) & (1ULL <<  4) ?  4 :	\
		(n) & (1ULL <<  3) ?  3 :	\
		(n) & (1ULL <<  2) ?  2 :	\
		1 ) :				\
	(sizeof(n) <= 4) ?			\
	__ilog2_u32(n) :			\
	__ilog2_u64(n)				\
 )

透過 Github 搜尋欄位查詢到在 [linux/lib/math/div64.c](https://github.com/torvalds/linux/blob/master/lib/math/div64.c#L193) 當中有應用到 `ilog2` 這個巨集。

#ifndef mul_u64_u64_div_u64
u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c)
{
	u64 res = 0, div, rem;
	int shift;

	/* can a * b overflow ? */
	if (ilog2(a) + ilog2(b) > 62) {
        ...

`mul_u64_u64_div_u64` 函式當中運用 `ilog2` 巨集來判斷兩數 a, b 是否在相乘之後是否會溢位。

### 測驗五
測驗五是測驗三的延伸，改變的點是添加了 ceilling 的功能。

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}

`r` 以及 `shift` 是用作紀錄因給定數字 `x` 分別大於 `0xFFFF`, `0xFF`, `0xF`, `0x3` 的時候，需要進行下一步判斷需要位移的數量。

其中 `r`, `shift` 都是 2 的指數所以 `r | shift` 就相當於 `r + shift`。

最後的 `x > 1` 是為了判斷 `x` 若是大於 1 且小於等於 0x3 時的狀況。

### 測驗五延伸問題
#### 判斷 `x = 0` in branchless

若是 `x` 為 0，在進入函式一開始的時候會因為 `x--` 變成 0xFFFFFFFF，所以在做減法前就需要判斷是否為 0。

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

+   x -= (x > 0);
-   x--;

> commit: [0095464](https://github.com/brian049/Linux_quiz_code/commit/0095464b9d384b40b2cd85d3e8b1d0199472fb0e)