# 2024 Homework4 (quiz3+4)
contributed by <HotMercury>

## 第 3 週測驗題
### isqrt1: bitwise 操作
在執行第一版 `i_sqrt` 時嘗試使用 `gcc` 編譯，有以下錯誤，但如果把 n 變成常數，就可以正常執行，[error In using math function in gcc?](https://stackoverflow.com/questions/15737932/error-in-using-math-function-in-gcc) 可以知道如果使用的是 const 編譯器會最佳化成對應的值，如果要正確執行要加上 `-lm` link math library.

- int msb = (int)log2(n);
+ int msb = (int)log2(16);

$ gcc sqr_t.c    
/usr/bin/ld: /tmp/ccmYLpqw.o: in function i_sqrt:
sqr_t.c:(.text+0x23): undefined reference to log2

[第一版的方式](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1) 可以得知 $\log{n}$ 與 $\sqrt{n}$ 間的大小不會影響答案。
> 這裡做更正我原本以為的作法是找到最靠近且略小於 $\sqrt N$ 的方式再繼續找，但現在發現是找到 N 向上取 $log_2 -1$ 這樣可以確保最高位，之後再以 2 的冪逼近。

$$
\log_2{n} < \sqrt{n}, n >= 16
$$


接下來思考如何不透過 `log` 也可以保有原有的精度，isqrt2 就是透過 shift 方式判斷 MSB 在第幾位。

#### 直式開方
上述 isqrt1 和 isqrt2 都是逐位元搜尋，且乘法成本太高，接下來可以使用 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 直式開方的方法。

跟著[公式](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1)實際推演
$P_0$ 及為我們想要求的平方根，所以我們從最高位慢慢遞減 $P_m$。
$$
P_0 = a_n + a_{n-1} + ... + a_0
$$

但不想要透過成本過高的乘法，因此使用上一輪差值 $X_{m-1}$ 減去($P_m^2 - P_{m+1}^2$) : $Y_m$
$Y_m$ 又由以下組成
- $c_{m-1} = \begin{cases} c_m/2 + d_m & if \ a_m = 2^m \\ c_m/2 & if \ a_m = 0 \end{cases}$
- $d_{m-1}= d_m/4$

程式邏輯
- $X_{n+1} = N$
- $c_n = 0$ 一開始還沒有值
- $d_n = ({2^m})^2$

先透過 `__builtin_clz` 找到 msb, 在依據上述數學式完成，以下為對應代號程式碼

int i_sqrt3(int n)
{
    if (n <= 1) /* Assume n is always positive */
        return n;

    int c = 0;
    for (int d = 1UL << ((31 - __builtin_clz(n)) & ~1UL); d; d >>= 2) {
        int y = c + d;
        c >>= 1;
        if (n >= y)
            n -= y, c += d;               
    }
    return c;
}

#### 改寫第三版程式

1. 直接透過 C library 的方式呼叫 `ffs`
[commit 575c64b](https://github.com/HotMercury/2024_linux_quize/commit/575c64bd18918b7263775221282c5882511ea94a)
2. 使用[第二周測驗](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)用到的 `__ffs` 函式可以應用在 32 位元的參數
這裡先只用 32 位元，因此先不啟用 #define BITS_PER_LONG 64，這裡用的方式是 binary search 的變形，透過 bitwise 的操作可以減少次數，以 `i_sqrt1` 為例子，需要一個一個右移，而 binary 只需要以 2 的冪來尋找。
[commit 2fffd11](https://github.com/HotMercury/2024_linux_quize/commit/2fffd11fe8dc6d897a86ed66c012efa6d289f8b7)

3. 不使用到 branch，使用 bitwise 的方式
a. 先將第一個為 1 的位置以後都設成 1
b. 透過 bitwise 算出總共有多少個 1 bit
c. total bit - 算出的 bit 數

#### [block](https://github.com/torvalds/linux/tree/master/block) 應用到程式碼
我在 [`block/blk-wbt.c`](https://elixir.bootlin.com/linux/latest/source/block/blk-wbt.c#L409) 中找到 `rwb_arm_timer` 會使用到 `int_sqrt`，接下來要嘗試理解這個 function 在做什麼。為了測試我能不能有觀察 linux kernel 的 sense，我先單純看 function 來猜測，以 block 底下來說 rwb 可能就是 request write back，接下來 arm 跟 timer 就是 arm 架構下 write back 的時間，以上猜測時間結束。
**trace code**
第一步嘗試去找誰呼叫了這個 function，`wb_timer_fn` and `wbt_wait`但可惜的是資料結構太多且不熟悉用途，所以從 `rwb_arm_timer` 程式碼下手，先拿到 `struct rq_depth` 可以從裡面得知會有兩種情況來調整 window size(這裡還不知道是什麼，目前猜是時間)
- 當 scale_step > 0 ：會算出新的 window size
- 否則照舊

在計算新的 window size 裡註解有提到 `We should speed this up` 所以目前是認為這個是特定方式的運算，之後提到 [fast integer inverse square](https://en.wikipedia.org/wiki/Fast_inverse_square_root) 是一個計算 $\frac{1}{\sqrt{x}}$ 的方法，

static void rwb_arm_timer(struct rq_wb *rwb)
{
	struct rq_depth *rqd = &rwb->rq_depth;

	if (rqd->scale_step > 0) {
		/*
		 * We should speed this up, using some variant of a fast
		 * integer inverse square root calculation. Since we only do
		 * this for every window expiration, it's not a huge deal,
		 * though.
		 */
		rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
					int_sqrt((rqd->scale_step + 1) << 8));
	} else {
		/*
		 * For step < 0, we don't want to increase/decrease the
		 * window size.
		 */
		rwb->cur_win_nsec = rwb->win_nsec;
	}

	blk_stat_activate_nsecs(rwb->cb, rwb->cur_win_nsec);
}

看到一個很有趣的 patch [blk-wbt: fix a divide-by-zero error in rwb_arm_timer()](https://lkml.indiana.edu/hypermail/linux/kernel/2104.2/01733.html) 之後嘗試理解

### Testing 2 : 減少 mod 10 和 div 10 操作
針對字串加法，暴力法可以通過 carry bit 的方式往前累進，所以一次運算會用到一次除法(for carry) 與 mod 運算，接下來參考《[Hacker's Delight](http://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)》我們想用 bitwise 的方式取代 divide and mod operation。
想要透過 bitwise 計算的方式一定是 $\frac{an}{2^N}$ (因為分母要用 shift 的方式)，計算出符合 $1.9 \leq \frac{19}{x} \leq 1.99 \Longrightarrow 9.55 \leq x \leq 10$ 目前 a : 13, $2^N$ : 18，只要在範圍內就可以，( 這裡教材寫只要判定最大的不會超過就好，這個還需要理解 )。
再來我們的目標就是要乘 13 除 128，這裡我一開始想到的是直接使用乘法，但這裡將 13 拆分為 2 進位的方式，以此達到乘 13 的效果，底下為 $\frac{13tmp}{8}$

(tmp >> 3) + (tmp >> 1) + tmp) << 3)

而以下說明一個問題，即右移後，會有部分位元被捨棄，因此要另行處理。並不是很清楚為什麼是拿 q 來右移且要加三個，所以我嘗試用定點數的方式來計算。

- ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2)
// 使用 Q3 的方式
+ q = n + (n << 2) + (n << 3);
+ q = q + (1 << (3 - 1));

如何解出以下的 code
- $x = \frac{4}{5} \times in$
- $q = \frac{17}{16} \times x$

其他的還沒想出來

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> CCCC);
    *mod = in - ((q & ~0x7) + (*div << DDDD));   
}

#### 解析 CPU 週期數量

## 第 4 週測驗題
### Testing 3
#### rbtree

`udpate` 不要太頻繁