# 2024q1 Homework4 (quiz3+4)
contributed by < [`hugo0406`](https://github.com/hugo0406) >

## [第三周測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗一

### 測驗二

### 測驗三
**版本一**

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

版本一透過右移的操作來得到 $\lfloor lg(i) \rfloor$ ，每當右移一個位元，就對 log 加一，直到找到最高位元。然而當 i 的數值越大，迴圈進行的次數也會越多。

**版本二**

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

版本二是將版本一進行改善，透過判斷條件一次右移多個位元來減少迴圈次數。

**版本三**

$\lfloor lg(i) \rfloor$ 的值取決於 i 的 msb 的位置 ，舉 i = 79 為例 ， i 的 msb 的位置為 6 ， $\lfloor lg(i) \rfloor$ 為 6

    31 30 29 28 ... 10 9 8 7 6 5 4 3 2 1 0      // bit position
     0  0  0  0      0 0 0 0 1 0 0 1 1 1 1      // i=79
                             ^ 
                            msb 

可以用 GNU extension `__builtin_clz` 來得到 msb 前有幾個 0，透過 $31-clz(i)$ 可得到 msb 的位置，也就是 $\lfloor lg(i) \rfloor$ 的值。

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(DDDD)); //DDDD = V | 1
}

[ Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 有對 `__built-in_clz` 進行說明，說明如下
> Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

若輸入值為 0 則無定義，因此透過 `V | 1` 能確保值不為零。

**Linux 核心原始程式碼**

### 測驗四

### 測驗五

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 > GGG) + 1;  // GGG = 1      
}

這段程式碼的運作原理類似於測驗三的版本二，透過數值比較來決定要右移多少個位元，得出
$\lfloor lg(x) \rfloor$，由於函式要求出 $\lceil lg(x) \rceil$ ，因此要把結果進行加一再回傳。

注意到 `x--` ，是為了要特別處理 2 的冪次方，分析如下:
若 x 為 2 的冪次方 ，則 $\lceil lg(x) \rceil =\lfloor lg(x) \rfloor =lg(x)$
若 x 非 2 的冪次方 ，則 $\lceil lg(x) \rceil = \lfloor lg(x) \rfloor + 1$
透過 `x--` ，這樣可以避免若 x 為 2 的冪次方結果不正確會多 1 的情形。

**程式碼改進**

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

-   x--;
+   x = (x == 0) ? 0 : 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 > GGG) + 1;  // GGG = 1      
}

原程式碼若輸入 0 ，則在 `x--` 就會發生 underflow ，會導致結果不正確。
作業要求改善使其能處理 x = 0 的狀況，並仍是 branchless ，可以透過三元運算子來達到。

# [第四周測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)

### 測驗一

### 測驗二