---
tags: NCKU Linux Kernel Internals, C語言
---
# C 語言：數值系統
[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80%EF%BC%9A%E6%95%B8%E5%80%BC%E7%B3%BB%E7%B5%B1%E7%AF%87)
## bit-wise operator
觀察與學習不同bit-wise operator的神奇操作，以後在閱讀kernel code時就可以保持對程式的敏感度(~~希望啦~~)
### 取絕對值的常數實作
如果要實作一個計算絕對值的函式
```c=
#include <stdint.h>
int32_t abs(int32_t x){
if(x>0)
return x;
else
return -x;
}
```
顯而易見的設計，但程式中產生了branch。
思考一下
$$
abs(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
-x & \text{if } x < 0
\end{cases}
$$
等價於
$$
abs(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
(\sim x) + 1 & \text{if } x < 0
\end{cases}
$$
我們可以通過~x (反轉全部位元)即是對 0xFFFFFFFF 做 XOR 操作的特性來改寫。
簡單考慮到32位的signed int時，向右位移採用[算數位移](https://en.wikipedia.org/wiki/Arithmetic_shift)。則:
* 若輸入值是正整數，那麼:
* A = 輸入值 >> 31 得到 0x00000000 => 0
* B = -A 得到 -0x00000000 => 0
* 若輸入值是負整數，那麼:
* A = 輸入值 >> 31 得到 0xFFFFFFFF => -1
* B = -A 得到 0x00000001 => 1
因此就可以將abs改寫成
``` c=
#include <stdint.h>
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x + mask) ^ mask;
}
```
### 取最小值的常數操作
如何設計一個得到可以最小值的，沒有分支的函式？
```c=
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
思考上面的式子，我們可以把a-b分成三種情況：
* a - b = 0
* (0 & (0 >> 31))
* return b
* a - b > 0:
* diff最高位為0，因此右移31bit = 0
* (diff & 0) = 0
* return b
* a - b < 0:
* diff最高位為1，因此右移31bit = 0xFFFFFFFF(注意是算術位移)
* (diff & 0xFFFFFFFF) = diff = (a - b)
* return b + (a - b) = a
更多細節請閱讀: [解讀計算機編碼](https://hackmd.io/vOjbtew3Tn2aA0uDrmUL4Q?view#%E8%A7%A3%E8%AE%80%E8%A8%88%E7%AE%97%E6%A9%9F%E7%B7%A8%E7%A2%BC)
### `x & (x - 1) == 0`
[X = X & X-1 Trick](http://sevensavants.blogspot.com/2010/01/x-x-x-1-trick.html)
* 判斷x是不是2的N次方(無號數)
* 如果一個數字是2的N次方，那麼其二進位表達的最高位為1，其餘位為0。
* 換個角度思考: 讓某個值少 1，就是讓那個值對最右邊的1產生借位。`x & (x - 1)`實際上是在**把二進位表示中最靠右邊位的1變成0**，而2的N次方**最右邊的1 = 最高位的1**
``` c=
int foo(unsigned int x)
{
int count = 0;
while(x)
{
count++;
x = x&(x-1);
}
return count;
}
```
如果你理解的話，應該可以知道這個函式的功用就是**計算x的二進位表示式中包含1的數量**(把最x右邊的1移除直到x=0)。
### ASCII table
ASCII table的安排大有學問，你可以發現 'A' 和 'a' 相差剛好32。~~巧合嗎？我可不這麼認為~~
* 大A到大Z: 0b1<font color=red>0</font>0 0001 到 0b1<font color=red>0</font>1 1010
* 小a到小z: 0b1<font color=red>1</font>0 0001 到 0b1<font color=red>1</font>1 1010
因此將字元轉成小寫
``` c=
('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'
```
將字元轉為大寫:
``` c=
('a' & '_') // 得到 'A'
('A' & '_') // 得到 'A'
```
### [XOR Swap](https://en.wikipedia.org/wiki/XOR_swap_algorithm)
用3個XOR，不需要額外的空間交換數值。
* XOR的同等運算: `x ^ y == (~x & y) | (x & ~y)`
### 避免 overflow
* 計算`(x + y) / 2`，如果x + y的時候產生overflow，就會出錯了
```
(x & y) + ((x ^ y) >> 1)
```
* 用加法器來思考: x & y 是進位, x ^ y 是位元和。
* 則 `x + y = x ^ y + ( x & y ) << 1`
* `(x + y) / 2 `
= `(x + y) >> 1 `
= `(x ^ y + ((x & y) << 1))>>1`
= `((x ^ y) >> 1) + (x & y)`
### Detect NULL
``` c=
#if LONG_MAX == 2147483647L
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
#define DETECT(X) \
(((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
```
這個macro的功用是偵測是否為0(是否為 NULL char ’\0’)。(詳細請看老師的教材!相當有趣XD)
## Count Leading Zero
Couting leading zero會被使用在甚麼地方?
如果我們想要對一個用 n 位元表示的數字計算 log2 (取整)，只要找到 "最左邊有幾個 0 " 就可以了，用 n-1 減掉即可。為了方便了解，我們以 8 bits 為例，擴展到 32 / 64 bits 則同理:
* 4 = 0b00000100 = 7 - 5 = 2
* 7 = 0b00000111 = 7 - 5 = 2
把32位元的無號數直觀的寫成程式就是:
``` c=
for (bits = 32; bits > 0; --bits) {
if (n & 0x80000000) break;
n <<= 1;
}
return bits;
```
然而，我們可以透過一些技巧減少運算的時間。
* iteration: 每個iteration都把 x "折成一半"，如果上半部有 1，接下來就找上半部即可;反之，只要找下半部就好。
```c=
int n = 32, c = 16;
do {
uint32_t y = x >> c;
if (y) { n -= c; x = y; }
c >>= 1;
} while (c);
return (n - x);
```
* binary search technique:
```c=
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 0;
if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
return n;
}
```
* byte shift:
``` c=
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 1;
if ((x >> 16) == 0) { n += 16; x <<= 16; }
if ((x >> 24) == 0) { n += 8; x <<= 8; }
if ((x >> 28) == 0) { n += 4; x <<= 4; }
if ((x >> 30) == 0) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
還有更複雜的如[De Bruijn32](https://en.wikipedia.org/wiki/De_Bruijn_sequence)的作法。請直接參閱課程。
## Round Up / Down Power-of-2
> [2021q1 第 2 週測驗題: 測驗二](https://hackmd.io/@sysprog/linux2021-quiz2#%E6%B8%AC%E9%A9%97-2)
下面所展示的 `rounddown_pow_of_two` 可以接受 16 位元的無號整數 `N`，並回傳小於(且最接近)或等於 `N` 的 power-of-2，為甚麼呢?
```cpp
uint16_t rounddown_pow_of_two(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
return (N + 1) >> 1;
}
```
試想一下我們可以怎麼做到 `rounddown_pow_of_two` 要求的行為，首先，這個問題其實相當於在找最高位的 1 在哪，所以我們其實可以用 [gcc builtin](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的 `__builtin_clz` 來實作:
```cpp
uint16_t rounddown_pow_of_two2(uint16_t N){
// the input of clz is unsigned int
if (N == 0)
return 0;
return 1 << (31 - __builtin_clz(N));
}
```
:::info
1. N == 0 預期的行為沒定義，可以先忽略
2. 因為 `__builtin_clz` 接受的型態是 unsigned int，所以這裡用 31 去減
:::
換個想法的話，假設最高位的 1 在第 k 位，那麼我們可以先把最高位的 1 往後的位元都設成 1，然後再將結果加 1 後右移 1 位，也可以得到想求得的答案。例如 $21_{10}$ = $10101_{2}$，先把往後的位元都設成 1，也就是 $11111_2$ ，然後再計算 $(11111_{2} + 1) >> 1 = 16_{10}$。
此時你應該發現了，後面的計算其實就對應 `(N + 1) >> 1`，因此前面的一系列 `|` 和 `>>` 所做就是把後面的位元填成 1。為甚麼這些操作可以把最高位的 1 往後的位元都填成 1 呢? 首先我們可以先想得簡單一點，因為 `|` 右移後的數值必定不會改動到最高位元的 1 往前的位元，所以最直接的實作是:
```cpp
uint16_t rounddown_pow_of_two0(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 3;
...
N |= N >> 14;
N |= N >> 15;
return (N + 1) >> 1;
}
```
但是事實上不需要執行那麼多次，思考最極端的狀況 $1000000000000000_2$
* `N |= N >> 1` 變成 $1100000000000000_2$
* `N |= N >> 2` 變成 $1111000000000000_2$
* `N |= N >> 4` 變成 $1111111100000000_2$
* `N |= N >> 8` 變成 $1111111111111111_2$
可以看到每一次的 `|` 和 `>>` 操作都可以增加最多 2 倍的 1，因此最極端有 15 個零需要填成 1 的情況下也只要 4 次操作，增加 $2^4=16$ 倍的 1 就可以將最高位元以後的所有位元填成 1。
在此之外，思考一下上面的例子中 `N` 的適用(可以得到正確結果)範圍為何呢? 以 `uint16_t` 的版本為例，假如輸入 N = 0x80，最後 return 時的 $1111111111111111_2$ + 1 已經超過 `uint16_t` 可表示範圍，但最終卻可得到正確得結果 0x80。與之相對的，在 `uint32_t` 的版本:
```cpp
uint32_t rounddown_pow_of_two(uint32_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
N |= N >> 16;
return (N + 1) >> 1;
}
```
如果輸入 N = 0x80000000，最後 return 時卻無法得到正確的結果 0x80000000，造成這個情形的原因是甚麼呢?
答案其實就藏在 [C 語言規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf?fbclid=IwAR2k5K3ZPS4CzQ9AbVS96QD-5N2UQyE23Ui4ic270JX5Df3pEXJkg1cBDHA) 中。根據 6.3.1.1 Boolean, characters, and integers 的第 2 點:
> if an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. All other types are unchanged by the integer promotions.
因此，`uin16_t` 型態的 N 在 expression 中會先被 promote 成 `int` 型態(假設 [data model](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 中 `int` 為 32 bits)，計算後再轉回 16 bits 型態回傳。與此相對的，`uint32_t` 沒有被隱性的轉換到更高的 bits 表示，因此 `(N + 1)` 產生 overflow，得到非預期的結果。
## Linux 中的 bitwise 操作
下面，嘗試研讀幾個 Linux 系統中重要的 bitwise 操作技巧。
### log2
在 [include/linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 可見到與 log2 相關的 bitwise 操作。
#### `is_power_of_two`
```cpp
/**
* is_power_of_2() - check if a value is a power of two
* @n: the value to check
*
* Determine whether some value is a power of two, where zero is
* *not* considered a power of two.
* Return: true if @n is a power of 2, otherwise false.
*/
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
```
恰如其名，這個函式可以用來判別 `n` 是否為 $2^k$(k 為整數)，而其實作技巧事實上就是前面曾經提到的 `x & (x - 1)`。
* [`__attribute__((const))`](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124974244.htm) 提示此函數對於相同數值的輸入可以得到同樣的結果，且也不影響 global 的任何記憶體，使得編譯器可以進行必要的優化。
#### `__rounddown_pow_of_two` / `__roundup_pow_of_two()`
```cpp
/**
* __rounddown_pow_of_two() - round down to nearest power of two
* @n: value to round down
*/
static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
return 1UL << (fls_long(n) - 1);
}
```
`__rounddown_pow_of_two()` 的作用如前所述，但是實作的思維上不同。`fls_long` 定義在 [linux/include/linux/bitops.h](https://github.com/torvalds/linux/blob/master/include/linux/bitops.h) 中
```cpp
static inline unsigned fls_long(unsigned long l)
{
if (sizeof(l) == 4)
return fls(l);
return fls64(l);
}
```
`fls` 意指 find last set bit，根據硬體的不同可能有不同的實作方式。 不過想法近似於此前我們曾用 `__builtin_clz` 實作的版本，找到最高位的 1 之位置 `i`(注意位置是位置的範圍是 1 ~ 64)，則所求就是 $2^{i-1}$
```cpp
/**
* __roundup_pow_of_two() - round up to nearest power of two
* @n: value to round up
*/
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
return 1UL << fls_long(n - 1);
}
```
與 `__rounddown_pow_of_two()` 相對，找到大於等於(且最接近)的 power of two
## TODO
- [ ] 閱讀 [CS:APP 第 2 章重點提示和練習](https://hackmd.io/@sysprog/CSAPP-ch2#%E6%95%B8%E5%80%BC%E7%B3%BB%E7%B5%B1)並透過練習題深入學習
Sign in with Wallet
Connect another wallet