---
tags: linux2023
---
# 第 7 週課堂問答簡記
## yanjiew1
[Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)
## DokiDokiPB
[quiz4](https://hackmd.io/@DokiDokiPB/linux2023q1-quiz4)
> 留意 LLRB 和典型 rbtree 的落差，見[關於紅黑樹](https://hackmd.io/@yanjiew/rbtree01)
## qwe661234
[fibdrv](https://hackmd.io/@qwe661234/linux2022q1-homework3)
## zeddyuu
[fibdrv](https://hackmd.io/@zeddyuu/linux2023q1-fivdrv)
[quiz4](https://hackmd.io/@zeddyuu/q4)
## fennecJ
>l_offt 在 linux 中的定義是什麼 type?
在 [fibdrv.c](https://github.com/qwe661234/fibdrv/blob/master/fibdrv.c#L231) 使用到 `l_offt` 作為參數型態，可能發生什麼潛在的問題
`src`: linux v6.2.8
`l_offt`:
defined in
`include/linux/types.h` L46
```c=45
#if defined(__GNUC__)
typedef __kernel_loff_t loff_t;
#endif
```
`__kernel_loff_t`:
defined in
`include/uapi/asm-generic/posix_types.h` L88
```c=88
typedef long long __kernel_loff_t;
```
long long 的 range 為
`-9223372036854775808` ~ `9223372036854775807` ，loff_t 單位為 byte ， $\approx ± 8388608$ TiB
>kernel module 計算完 big num 之後是怎麼把資料傳到 user space 的 ？
>
用 `__copy_to_user` 這個 kernel API 。
>那這個 API 最後面參數的 size 範圍有多大。
最後一個參數的型別為 unsigned long ，在 LP64 的機器上是 64bit 的寬度。
>對，linux 在處理這個議題的時候是尊重使用者電腦的架構決定寬度，若在 32 位元的機器上 unsigned long 的寬度則會是 32 位元。
## chun61205
針對正整數在相鄰敘述進行 mod 10 和 div 10 操作，如何減少運算成本？
```c
static void string_number_add(char *b, char *a, char *res, size_t size)
{
int carry = 0;
for (int i = 0; i < size; i++) {
int temp = (b[i] - '0') + (a[i] - '0') + carry;
carry = temp / 10;
temp = temp % 10;
res[i] = temp + '0';
}
}
```
### 利用除法原理將 mod 10 和 div 10 合併
根據除法原理：
$f = g \times Q + r$
* $f$: 被除數
* $g$: 除數
* $Q$: 商
* $r$: 餘數
可以將 mod 10 和 div 10 合併，以此來減少除法的數量。
```c
carry = temp / 10;
temp = temp - carry * 10;
```
### 利用 bitwise operation 來去除除法運算
這裡參考了 [Hacker's Delight](http://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 來實作除法。
#### 探討精確度
這裡採用 bitwise operation 來實作除法，因為 $10$ 有包含 $5$ 這個因數，無法完全用 $2$ 的次方項來表示，因此結果會是不準確的。然而，觀察上面的程式碼後可以發現， `temp` 不可能會大於 `19` ，因此只需要考慮 `19`~`0` 的情況即可。
我們的目標是，得到 `temp / 10` 且直到小數點後第一位都是精準的。
這時，我們可以提出一個猜想，假設我們我們目標的最大數是 `n` ， `l` 則是比 `n` 還要小的非負整數。那麼假設 $n=ab$ ($a$ 是十位數 b 是個位數)，且 $l=cd$ ($c$ 是十位數，$d$ 是個位數)，則只要以 $n$ 算出來的除數在 $n$ 除以該除數後在經確度內，則 $l$ 除與該除數仍然會在經確度內。證明如下：
假設 $x$ 是除數，
$$
a.b\leq\frac{n}{x}\leq a.b9\\
\Rightarrow\frac{n}{a.b9}\leq x\leq\frac{n}{a.b}
$$
1. 這裡可以很明顯的看出 $x$ 的右邊是 $10$ ，因此一定在精確度內。
2. $x$ 的左邊：
$$
c.d\leq l\times\frac{a.b9}{n}\leq c.d9\\
\Rightarrow c.d\leq cd\times\frac{a.b9}{ab}\leq c.d9\\
$$
1. $cd\times\frac{a.b9}{ab}$ 的左邊顯然成立
2. $cd\times\frac{a.b9}{ab}$ 的右邊：
$$
c.d + \frac{0.09cd}{ab}\leq c.d + 0.09
$$
因為 $ab > cd$ 因此上述式子依然成立。
因此，當初我的猜想也成立，接下來只需要針對 `19` 來做討論即可。
$$
1.9\leq \frac{19}{x}\leq 1.99\\
\Rightarrow 9.55\leq x\leq10
$$
接下來只需要找到這之中可以用除法來表示的除數即可。
#### 找到除數
方法如下，透過 bitwise operation 得到的算式必定是 $\frac{an}{2^N}$ 其中 $N$ 為非負整數， $a$ 正整數。因此只需要透過查看 $2^N$ 再配對適合的 $a$ 即可。
其中， $2^N=128, a=13,\frac{128}{13}\approx9.84$ 便是一個可以使用的解。
#### 實作除法
接著，嘗試透過 bitwise operation 來配對數字。
```c
unsigned d2, d1, d0, q, r;
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2) >> 7;
r = temp - (((q << 2) + q) << 1);
```
關於這段程式碼，我的思路如下：
1. 先湊出 $13$：
觀察 $13$ 後可以發現， $13=8+4+1=2^3+2^2+2^0$ ，因此，首先要做的便是，使用 bitwise operation 得到 $\frac{13temp}{8}$
$\frac{temp}{8}+\frac{temp}{2}+temp$
```c
(temp >> 3) + (temp >> 1) + temp
```
2. 這時會發生一個問題，也就是在 right shift 後，會有部分 bits 被忽略，因此必須將它們另外考慮進來。
```c
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
```
3. 合併步驟 1, 2
```c
((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2)
```
4. 湊出 $128$ ，也就是右移 $7$ bits
```c
q = ((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2) >> 7;
```
5. mod 10 就是 `temp` 減去 div 10 的結果乘與 $10$
```c
r = temp - (((q << 2) + q) << 1);
```
其中 `(((q << 2) + q) << 1)` 就是 ($q\times 4 + q)\times2$ 也就是 $10\times q$
測試結果如下：
```c
#include <stdint.h>
#include <stdio.h>
int main()
{
for(int n = 0; n <= 19; n++){
unsigned d2, d1, d0, q, r;
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
r = n - (((q << 2) + q) << 1);
printf("q: %d r: %d\n", q, r);
}
return 0;
}
```
```shell
q: 0 r: 0
q: 0 r: 1
q: 0 r: 2
q: 0 r: 3
q: 0 r: 4
q: 0 r: 5
q: 0 r: 6
q: 0 r: 7
q: 0 r: 8
q: 0 r: 9
q: 1 r: 0
q: 1 r: 1
q: 1 r: 2
q: 1 r: 3
q: 1 r: 4
q: 1 r: 5
q: 1 r: 6
q: 1 r: 7
q: 1 r: 8
q: 1 r: 9
```
結果正確。
可包裝為以下函式:
```c
#include <stdint.h>
void divmod10(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 >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));
}
```
使用案例:
```c
unsigned div, mod;
divmod10(193, &div, &mod);
```
延伸閱讀:
* [Modulus without Division, a tutorial](http://homepage.cs.uiowa.edu/~dwjones/bcd/mod.shtml)
Sign in with Wallet
Connect another wallet