2022q1 Homework3 (quiz3)

contributed by < jj97181818 >

測驗 1

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

因為這裡的 unsigned long 為 8 bytes，所以 ~0UL 有 64 bit 的 1。
先討論 ((~0UL) >> (LEFT))，為了讓連續的 bitmask 最高位到 h 停止，又因 LSB 從第 0 位開始算起，MSB 是第 63 位，所以需要讓 64 bit 的 1 向右移 63 - h 位。
再來看 ((~0UL) >> (l) << (RIGHT))，先將 64 bit 的 1 向右移 l 位，為了讓連續的 bitmask 最低位從第 l 位開始，就再左移 l 位，其餘會補 0，就實現從第 l 位開始。
將 ((~0UL) >> (LEFT)) 和 ((~0UL) >> (l) << (RIGHT)) 做 AND 運算，即可同時滿足最高位到 h、最低位從 l 開始，即 GENMASK 巨集。

因此 LEFT = 63 - h, RIGHT = l

測驗 2

struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

to_fd 要將指定的位址 v 當作 fd 的起始位址，且要確保以 4 bytes 向下對齊，而向下對齊的巨集：

#define align_down(x) ((x) & ~(MAX_ALIGNMENT - 1))

v & ~(4 - 1) = v & ~3 = v & 1100
透過將位址 v 的最後兩位 clear 掉，來保證該位址一定為 4 的倍數，做到向下對齊。

因為該位址是 fd 的起始位址，會有個指向 fd 第一個成員 struct foo 的指標，所以會需要在位址前加上 (struct foo *)。

因此 EXP1 = (struct foo *)(v & ~3)

測驗 3

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

目標是從 12345678 變成 87654321（這裡的 1~8 都是代表著 0 或 1 的值，只是用 1~8 來表示比較能清楚看出 reverse 的過程）：

x = (x >> 4) | (x << 4);

 (12345678 >> 4) | (12345678 << 4)
= 00001234 | 56780000 
= 56781234

這行可以看出從 8 bit 的中間切成兩半，並互換。

x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);

 ((56781234 & 11001100) >> 2) | ((56781234 & 00110011) << 2)
= (56001200 >> 2) | (00780034 << 2)
= 00560012 | 78003400
= 78563412

這行接著上一行切兩半的方式，先用遮罩 0xCC 取得原本位在 1, 2, 5, 6 的值，那 EXP2 的位置一定需要保留 3, 4, 7, 8 的位置，才能讓 x 保留原本 1~8 位置的所有值，因此這裡選用 0x33 當作遮罩，並左移兩位，在與 ((x & 0xCC) >> 2) 做 OR 運算時，即可保留所有資訊，並切從 4 bit 中間切成兩半做互換。

x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);

 ((78563412 & 10101010) >> 1) | ((78563412 & 01010101) << 1)
= (70503010 >> 1) | (08060402 << 1)
= 07050301 | 80604020
= 87654321

這行與上一行同樣的概念，只是改為每兩個 bit 中間切兩半做互換，可以看到這裡用的遮罩為 0xAA，並右移一位，而另外一個遮罩可以推得是 0x55，同樣要記得左移一位，就完成互換的動作了。從最初的 12345678 變成 87654321。

因此 EXP2 = (x & 0x33) << 2, EXP3 = (x & 0x55) << 1

測驗 4

#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[EXP4])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[EXP5],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

逗號運算子：(expression1, expression2)
首先計算表達式 1，然後計算表達式 2，並為整個表達式返回表達式 2 的值。

foreach_int macro 中，有個 for 迴圈：

初始條件：unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)
- ((int[]){__VA_ARGS__})[0] 為整數陣列，其中 __VA_ARGS__ 會填入 foreach_int 從第二個以後的參數，當作整數陣列的值，並取得整數陣列的第 0 個值，然後將值 assign 給 i
- 在逗號運算子的第一個表達式計算完成後，再將第二個表達式的值 0 回傳給 _foreach_i
繼續執行的條件：_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)
- sizeof((int[]){__VA_ARGS__}) / sizeof(int) 會得到整數陣列的元素數量
- 在 _foreach_i 小於元素數量時繼續執行迴圈
遞增：(i) = ((int[]){__VA_ARGS__, 0})[EXP4]
- 將 _foreach_i 先加 1，然後就可以讓 i 取得下一個整數陣列的元素
- EXP4 為 ++_foreach_i

foreach_ptr macro 中，也有個 for 迴圈：

初始條件：unsigned _foreach_i = (((i) = (void *)((typeof(i)[]){__VA_ARGS__})[0]), 0)
- ((typeof(i)[]){__VA_ARGS__})[0] 是一個型別為 typeof(i) 的陣列，然後取出陣列第 0 個位置的值，這個值可以預期傳入的是位址，因為這個巨集的名稱是 foreach_ptr
- ((i) = (void *)((typeof(i)[]){__VA_ARGS__})[0]) 將值強轉型為指向 void 的指標，然後 assign 給 i。
- 然後 0 assign 給 _foreach_i
繼續執行的條件：(i)
- 只要 i 不為 0 就會繼續執行迴圈
遞增：
- 和 EXP4 一樣的概念，EXP5 為 ++_foreach_i

(i) = (void *) ((typeof(i)[]){__VA_ARGS__, NULL})[EXP5],
_foreach_no_nullval(_foreach_i, i, ((const void *[]){__VA_ARGS__}))

因此 EXP4 = ++_foreach_i, EXP5 = ++_foreach_i

測驗 5

#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        EXP7;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

以 signal 來紀錄相除結果的正負號，然後如果除數或被除數為負整數，一律改為正整數。
shift 從 0 開始，當 dvd > (EXP6) 時，shift 加 1，因為這題目的是要做除法，這裡的 EXP6 一定會和除數 dvs 有關。這個迴圈會在 shift 愈來愈大之後在某個條件下停止，可想到的是將 dvs 左移 shift 位，當 shift 愈大，dvs 也愈大，直到超過或等於 dvd 的大小。這裡 shift 的意義是類似商的概念，看除數乘以多大的倍數（左移多少位）能夠比被除數大或至少相等。
在被除數 dvd 仍大於等於除數 dvs 時，表示可以繼續進行除法。當 dvs 左移 shift 位會比 dvd 大時，就將 shift 減 1。1 << shift; 的想法是將小於 dvd 並左移過後的 dvs 只取其最高位元，用 1 左移 shift 位來表達。
因為迴圈要 dvd 小於 dvs 才會停止，EXP7 要更新 dvd，而 dvd 減去 dvs 左移 shift 位，就是更新被除數，讓它減去除數乘以一個倍數。
當被除數 dvd 不再大於等於除數 dvs 時，相除的結果如果超出能表達的最大值，就直接回傳 INT_MAX。其餘則回傳除完的結果。

因此 EXP6 = dvs << shift, EXP7 = dvd -= dvs << shift

測驗 6

測驗 7

int ilog32(uint32_t v)
{
    int ret = v > 0; // 1,  0000 0001
    int m = (v > 0xFFFFU) << 4;  // 16 , 0001 0000
    v >>= m; 
    ret |= m; // 0001 0001
    m = (v > 0xFFU) << 3; // 8, 0000 1000
    v >>= m;
    ret |= m; // 0001 1001
    m = (v > 0xFU) << 2; // 4, 0000 0100
    v >>= m;
    ret |= m; // 0001 1101
    m = EXP10; // EXP10 = (v > 0x3U) << 1   2, 0000 0010
    v >>= m;
    ret |= m; // 0001 1111
    EXP11;
    return ret;
}

限制：

EXP10 和 EXP11 皆包含 > 運算子

ilog32 與 ffs 的實作很像，只是 ffs 是從 LSB 開始找第一個為 1 的 bit，這裡是從 MSB 找第一個為 1 的 bit。

最初的 ret = v > 0 是要記錄當 v > 0 時，最高位的 1 也需要一個位元儲存。
程式主體是做以下的操作 4 次。
- 更新 m
- 將 v 右移 m 位
- 更新 ret。
第一次先操作將 32 位元切半來看，比較高位元的 16 bit 中有沒有 1，有的話代表至少要儲存 16 bit（m = 16），然後將 v 右移 16 位，為的是方便繼續觀察原本較高位元的 16 bit 中還需要多少 bit 儲存。接著 ret 會記錄到目前為止共需要 16 bit 來存這個 v。
第二次就是將剩下 16 位元切半來看，看比較高位元的 8 bit 中有沒有 1，有的話代表至少要再多存 8 bit（m = 8），然後將 v 右移 8 位，方便繼續觀察原本較高位元的 8 bit 中還需要多少 bit 儲存。然後 ret 記錄到目前為止共需要 16 + 8 bit 來存這個 v。
接著第三次和第四次分別是看 8 位元中較高位元的 4 bit，和 4 位元中較高位元的 2 bit，因此 EXP10 為 (v > 0x3) << 1 才能查看較高位元的 2 bit 中是否有 1。
最後到 EXP11，只剩下最後兩位還沒判斷，如果 v > 1，那麼就代表最後兩位都需要儲存，而最高位元已經在最初的 ret = 1 就有加上一位了，所以只需要再加一位，EXP11 為 v > 1 時 ret 加上 1。

因此 EXP10 = (v > 0x3) << 1, EXP11 = ret += v > 1

測驗 8

測驗 9

ROUND_UP 巨集

向上對齊：

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - MMM) & ~(NNN))

向上對齊是利用位運算的方法，計算記憶體對齊後的大小，這裡的 MAX_ALIGNMENT 是 16 bytes，向上對齊會以 16 的倍數往上取。
例如：原本大小（這裡的 x）為 1~16 的變數，在向上對齊之後大小都會變成 16，17~32 會變成 32，33~48 會變成 48。
左段的程式 ((x) + MAX_ALIGNMENT - MMM) 是將大小加上 alignment 的大小再減去 MMM，要讓原本大小不足 16 的都補到 16。MMM 應該為 1，因為當 x = 16 時，x + MAX_ALIGNMENT = 16 + 16 = 32，會讓 16 在對齊後變成 32。
右段的程式 ~(NNN) 是要去除不足 16 的餘數，因為最後算出來的值應該是 16 的倍數。
當 NNN = MAX_ALIGNMENT - 1時：
~(MX_ALIGNMENT - 1)
= ~(15)
= 11110000
((x) + MAX_ALIGNMENT - 1) & ~(MAX_ALIGNMENT - 1)
= (x + 16 - 1) & 11110000
= (x + 00001111) & 11110000

因此 MMM = 1, NNN = MAX_ALIGNMENT - 1

ROUND_DOWN 巨集

向下對齊：

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \
    ((x) & ~(MAX_ALIGNMENT - 1))

因為向下對齊是將大小為 1~15 對齊成 0，16~31 對齊成 16，所以不需要加上 MX_ALIGNMENT 來補足不到 16 的餘數，不足的都直接不要了。

在 Linux 核心找出類似的巨集和程式碼

並說明 round-up/down 的應用場合

在 linux/include/linux/netfilter_bridge/ebtables.h 的第 107 行：

#define EBT_ALIGN(s) (((s) + (__alignof__(struct _xt_align)-1)) & \
		     ~(__alignof__(struct _xt_align)-1))

EBT_ALIGN 是做向上對齊。

測驗 10

#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

限制：

RRR 和 SSS 為表示式，且都包含 (__x) 和 (__d) (注意小括號)
RRR 和 SSS 限用 +, -, >>, << 這幾個運算子，可搭配小括號，並以符合 C99 的最精簡形式撰寫
變數在 RRR 和 SSS 出現的順序 (從左到右)，必定是 __x 先於 __d

先看三元運算子的條件
- ((typeof(x)) -1) > 0 在 x 的型別為 unsigned 的時候才會為 true
- ((typeof(divisor)) -1) > 0 在 divisor 的型別為 unsigned 的時候才會為 true
- (((__x) > 0) == ((__d) > 0)) 在兩個值皆大於 0 或小於 0 的時候，才為 true，也就是兩者同號為 true
當上述三元運算子的任一條件為 true，運算結果會是 ((RRR) / (__d))，即被除數或除數其中一個為 unsigned，或是兩者皆為有號數，但是同號。
當上述三元運算子的條件皆為 false，運算結果會是 ((SSS) / (__d))，即兩者皆為有號數，且不同號。
所以要找最接近該數字的整數做為商的話，最初的想法是將除完的小數加上 0.5，然後加完之後只取整數的部分。如果加上 0.5 能夠讓讓小數部分進位到整數的話，就代表原本小數後第一位是大於等於 0.5 的，也就是原本就比較靠近該數字取 ceil，即往上找最接近的整數。反之，該數字會比較靠近它取 floor，即往下找最接近的整數。
用題目給的例子來看：

DIVIDE_ROUND_CLOSEST(7, 3) = 2
- 7 除以 3 大約等於 2.3…，2.3 + 0.5 = 2.8
- 小數點後第一位並沒有進位到整數位，因此 2.3 往下找最接近的整數，即 2。或是 2.8 往下取最近整數。
DIVIDE_ROUND_CLOSEST(5, 3) = 2
- 5 除以 3 大約等於 1.6…，1.6 + 0.5 = 2.1
- 小數點後第一位有進位到整數位（整數從 1 變為 2），因此 1.6 往上找最接近的整數，即 2。或是 2.1 往下取最近整數。

接著要思考 RRR, SSS 各自要怎麼表達才能做到上面的想法。因為 ((RRR) / (__d)) 中我能改變的只有 RRR 的部分，所以我做了一些調整，變成：

RRR 的部分

以下四行的 / 先表示除到小數點後第一位
  floor((__x) / (__d) + 0.5)
= floor((__x) / (__d) + (0.5 * (__d)) / (__d))
= floor(((__x) + 0.5 * (__d)) / (__d))

因為 C 語言中的 / 本來就是無條件捨去小數點第一位，所以可以刪除 floor：
= ((__x) + 0.5 * (__d)) / (__d)
    
然後 0.5 * (__d) 可改成 (__d) >> 1
= ((__x) + (__d) >> 1) / (__d)

SSS 的部分
只有被除數和除數為異號時，才會執行到這。經過除法運算之後，因為值為負的，所以原本加 0.5，這裡要換成減 0.5，才能達到讓小數後第一位進位到整數的效果。

以下四行的 / 先表示除到小數點後第一位
  floor((__x) / (__d) - 0.5)
= floor((__x) / (__d) + ((-0.5) * (__d)) / (__d))
= floor(((__x) + (-0.5) * (__d)) / (__d))

因為 C 語言中的 / 本來就是無條件捨去小數點第一位，所以可以刪除 floor：
= ((__x) - 0.5 * (__d)) / (__d)
    
然後 (-0.5) * (__d) 可改成 -(__d) >> 1
= ((__x) - (__d) >> 1) / (__d)

因此 RRR = (__x) + (__d) >> 1, SSS = (__x) - (__d) >> 1

測驗 11

fls 是找最高位 1 的位置。

static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) {
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) {
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))
        num -= 1;
    return num;
}

參考 Digit-by-digit calculation

假設今天要求

N^{2}

的平方根 N，
定義

N^{2} = (a_{n} + . . . + a_{0})^{2}

，其中

a_{m}

會是

2^{m}

或

0

（用二進制的概念），
要從

P_{n}

一直迭代算到

P_{0}

，慢慢逼近要求的 N（

P_{i}

會愈來愈靠近 N）：

P_{n} = a_{n}

\to P_{n - 1} = a_{n} + a_{n - 1}

\to . . .

\to P_{m + 1} = a_{n} + a_{n - 1} + . . . + a_{m + 1}

\to P_{m} = a_{n} + a_{n - 1} + . . . + a_{m + 1} + a_{m}

\to . . .

\to P_{0} = a_{n} + a_{n - 1} + . . . + a_{m + 1} + a_{m} + . . . + a_{0}

由上可知：

P_{m} = P_{m + 1} + a_{m}

，而

a_{m}

會是

2^{m}

或

0

。

如果

P_{m}^{2} = (P_{m + 1} + 2^{m})^{2} \leq N^{2}

（加上了

2^{m}

也沒有超過

N^{2}

），則

a_{m} = 2^{m}

，且

P_{m} = P_{m + 1} + 2^{m}

；反之，則

a_{m} = 0

，且

P_{m} = P_{m + 1}

。

為了避免在每一輪算

P_{m}

的時候都要用

P_{m}

的平方去決定

a_{m}

是

2^{m}

或

0

，改用

X_{m} = N^{2} - P_{m}^{2}

（該輪

P_{m}^{2}

和原本的

N^{2}

還差多少，愈小代表

P_{m}

愈靠近

N^{2}

的平方根），
然後

X_{m} = X_{m + 1} - Y_{m}

（因為

P_{m}

可能會比

P_{m + 1}

來的更靠近 N，所以在與

N^{2}

的差異上，

X_{m}

可能會比

X_{m + 1}

小，其中

Y_{m}

是

X_{m}

和

X_{m + 1}

的差，是大於等於 0 的），
而

Y_{m} = X_{m + 1} - X_{m} = (N^{2} - P_{m + 1}^{2}) - (N^{2} - P_{m}^{2}) = P_{m}^{2} - P_{m + 1}^{2} = 2 P_{m + 1} a_{m} + a_{m}^{2}

。

上面有寫到會從

P_{n}

一直迭代算到

P_{0}

，首先是

P_{n} = a_{n}

，為了確認

a_{n}

是

2^{n}

還是

0

，將其代入

P_{m}^{2} = (P_{m + 1} + 2^{m})^{2} \leq N^{2} \to P_{n}^{2} = (0 + 2^{m})^{2} \leq N^{2}

，所以確認

a_{n} = 2^{n}

。

前面有提到

Y_{m} = 2 P_{m + 1} a_{m} + a_{m}^{2}

，將其分成

c_{m}

和

d_{m}

兩部分：
（在確定

a_{m}

為

2^{m}

而不是

0

後，

a_{m}

代入

2^{m}

）

c_{m} = 2 P_{m + 1} a_{m} = 2 P_{m + 1} 2^{m} = P_{m + 1} 2^{m + 1} d_{m} = a_{m}^{2} = (2^{m})^{2} Y_{m} = {\begin{cases} c_{m} + d_{m} & if a_{m} = 2^{m} \\ 0 & if a_{m} = 0 \end{cases}

更新

c_{m}

d_{m}

：

c_{m - 1} = P_{m} 2^{m} = (P_{m + 1} + a_{m}) 2^{m} = P_{m + 1} 2^{m} + a_{m} 2^{m} = {\begin{cases} c_{m} / 2 + d_{m} & if a_{m} = 2^{m} \\ c_{m} / 2 & if a_{m} = 0 \end{cases} d_{m - 1} = a_{m - 1}^{2} = (2^{m - 1})^{2} = \frac{d_{m}}{4}

當

c_{- 1} = P_{0} 2^{0} = P_{0} = N

此時 c 就是要求的平方根。

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) { 
        b = y + m;  //  Y_m = c_m + d_m
        y >>= 1;  //  c_m / 2

        if (x >= b) {  //  X_m >= Y_m
            x -= b;  //  X_{m-1} = X_m - Y_m
            y += m;  //  c_{m-1} = c_m + d_m
        }
        m >>= 2;  //  dm / 4
    }

    return y;
}

將程式中的 b 看成上述的

Y_{m}

，m 看成上述的

d_{m}

，x 看成上述的

X_{m}

，y 看成上述的

c_{m}

，程式就是在迴圈不斷地更新

c_{m}

和

d_{m}

。

因此 XXX = y >>= 1, YYY = x -= b, ZZZ = m >>= 2