---
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時就可以保持對程式的敏感度(~~希望啦~~)
### 取絕對值的常數實作
如果要實作一個計算絕對值的函式

    #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改寫成

#include <stdint.h>
int32_t abs(int32_t x) {
    int32_t mask = (x >> 31);
    return (x + mask) ^ mask;
}

### 取最小值的常數操作
如何設計一個得到可以最小值的，沒有分支的函式？

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**

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

因此將字元轉成小寫

('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'

將字元轉為大寫:

('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

#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位元的無號數直觀的寫成程式就是:

for (bits = 32; bits > 0; --bits) {
   if (n & 0x80000000) break;
    n <<= 1;
}
return bits;

然而，我們可以透過一些技巧減少運算的時間。
* iteration: 每個iteration都把 x "折成一半"，如果上半部有 1，接下來就找上半部即可;反之，只要找下半部就好。

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:

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:

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，為甚麼呢?

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` 來實作:

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 往前的位元，所以最直接的實作是:

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` 的版本:

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`

/**
 * 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()`

/**
 * __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) 中

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}$

/**
 * __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)並透過練習題深入學習