2022q1 Homework3 (quiz3)

contributed by < kevinshieh0225 >

作業需求
 測驗題目

測驗 `1` ：GENMASK

產生連續的 bitmask。

#define GENMASK(h, l) \
    (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))

(((~0UL) >> (63 - h)) 先填滿 bit 1，接著透過右移 (63 - h) 次，目的是清出左側的位元，做成左側遮罩。

((~0UL) >> (l) << (l))) 先填滿 bit 1，透過右移 l 次再左移 l 次，目的是清出右側的位元，做成右側遮罩。

兩者做 and 即可把左右遮罩結合，產生連續的 bitmask。

測驗 `2` ：align down

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

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

參考 <jim12312321> 針對向下對齊的說明。

依照測驗敘述：

函式 to_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 struct foo; 運用〈你所不知道的 C 語言：指標篇〉提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。

我們希望將 to_fd 指派在地址 v 向下對齊的位置上，故我們對 v 除以 4，以對齊在 4 的倍數的地址上。於是我們用 (v & -3) 達到此效果，並轉型為 foo pointer。

測驗 `3` ：Reverse Bits

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

我們以 x = 1234 5678 來表示一個無號八位元整數，數字代表原本字元的位置。0 代表該位元位置填入 0。

// 前後四位元交換位置。
x = 1234 5678;
x = (x >> 4) | (x << 4);
   0000 1234 | 5678 0000 => 5678 1234
       
// 分段前後兩位元交換位置
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
((5678 1234 & 1100 1100) >> 2) | ((5678 1234 & 0011 0011) << 2)
            ((5600 1200) >> 2) | ((0078 0034) << 2)
                   (0056 0012) | (7800 3400)
                          (7856 3412)

// 分段兩兩互換位元位置
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
((7856 3412 & 1010 1010) >> 1) | ((7856 3412 & 0101 0101) << 1)
            ((7050 3010) >> 1) | ((0806 0402) << 1)
                   (0705 0301) | (8060 4020)
                          (87654321)

測驗 `4` ：foreach macro

實作 foreach 巨集，第一個 parameter i 是迭代使用的變數或指標，隨後參數是迭代的值。

    int i;
    foreach_int(i, 0, -1, 100, 0, -99) {
        printf("i is %i\n", i);
    }
    const char *p;
    foreach_ptr(p, "Hello", "world") {
        printf("p is %s\n", p);
    }
/*
 * i is 0
 * i is -1
 * i is 100
 * i is 0
 * i is -99
 * p is Hello
 * p is world
 */

#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})[++_foreach_i])

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

語法特殊，逐步來看：

參考手冊 3.6 Variadic Macros

This kind of macro is called variadic. When the macro is invoked, all the tokens in its argument list after the last named argument (this macro has none), including any commas, become the variable argument. This sequence of tokens replaces the identifier __VA_ARGS__ in the macro body wherever it appears.

我們從 for 迴圈的起始、條件、動作拆分來看：

// start declaration
unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0);
unsigned _foreach_i = (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0);

將 __VA_ARGS__轉型成型態陣列，並將位置 0 的值指派給 i；將_foreach_i 視為 index 並指派為 0。

// end condition
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);
(i)

如果指標超過矩陣範圍，或是指向 NULL 則結束。

// step
(i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i]) 
(i) = (void *) ((typeof(i)[]){__VA_ARGS__, NULL})[++_foreach_i],   \
    _foreach_no_nullval(_foreach_i, i, ((const void *[])

將 i 指派新的索引值。特別注意這裡為了避免超出指標範圍，每次都擴增型態矩陣在最後插入 0。

測驗 `5` ：29. Divide Two Integers

#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;

測驗 `8` ：Binary search tree

void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            EXP12;
        else
            EXP13;
    }
    tnode *q = *p;
    if (!q)
        return;

    if (!q->left)
        *p = q->right;
    else if (!q->right)
        *p = q->left;
    else {
        tnode **r = &q->right;
        while ((*r)->left)
            r = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

測驗 `9` ：ROUND_UP_TO_ALIGNMENT_SIZE

在 data alignment 的章節提到，記憶體在抓取資料時會以 4 byte 為單位，於是資料為了讓資料讀取流程順利，會將資料配置在 4 的倍數的記憶體位置上。

資料對齊使的 struct 的成員們的記憶體地址可能不是連續的，而會做資料對齊。我們可以去調整結構中資料對齊的方式，比如使用 #progma pack來指定內部儲存對齊方式。

此函式實作給定一個記憶體大小值，我們希望回傳用如果我們用 MAX_ALIGNMENT = 16 來作對齊時，我們所需的總空間為何？

/* 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 - 1u) & ~(MAX_ALIGNMENT - 1u))

我們先思考一下這個實作的特性：我們給定一個對齊大小 = 16 ，並讓地址對齊此大小做配置。也就是說我們希望資料存放是以 16 的倍數為單位來放置的，並若不足向上補齊。

    1~16 -> 16, 17~32 -> 32

我們將此程式改寫為二進位理解：

    (xxxx xxxx + 0000 1111) & (1111 0000)
    
30: (0001 1110 + 0000 1111) & (1111 0000)
             -> (0010 1101) & (1111 0000) 
                           -> (0010 0000)
    // 後四位元 0001 -> 0010
66: (0100 0010 + 0000 1111) & (1111 0000)
             -> (0101 0001) & (1111 0000) 
                           -> (0101 0000)
    // 後四位元 0100 -> 0101
32: (0010 0000 + 0000 1111) & (1111 0000)
             -> (0010 1111) & (1111 0000) 
                           -> (0010 0000)
    // 後四位元 0010 -> 0010

前段做的是令未滿 16 的位元進位 1，後面在做的是除去未滿 16 的餘數。
故程式碼的用意是向上補齊至 16 的倍數，達到 allign 的效果。

在理解作用後，我們也能寫出 Round down 的程式碼：

#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    ((x) & ~(MAX_ALIGNMENT - 1u))

linux 中的 ALIGN

在 linux/include/linux/align.h 可見相同的程式實作。

測驗 `10` ：DIVIDE_ROUND_CLOSEST

此題實作整數除法取近似整數。

#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)))                         \
            ? (((__x) + ((__d) >> 1)) / (__d))                  \
            : (((__x) - ((__d) >> 1)) / (__d));                 \
    })

為何使用 typeof(x) __x = x; 先複製輸入變數呢？可參考前置處理器應用篇-block：因為巨集主要是在前置處理時期在程式碼中做展開。在這個程式中如果我們試想輸入參數為：

    result = DIVIDE_ROUND_CLOSEST(x++, divisor--)

那會導致預期想輸出的結果不同：x 和 divisor 在計算中途就被變更了。

        ? (((__x) + ((__d) >> 1)) / (__d))                  \
        : (((__x) - ((__d) >> 1)) / (__d));

這兩段條件回傳都是四捨五入取整數，一個是向正整數取值，一個向負整數取值。
為何這麼做能夠四捨五入呢？我們可以將以上程式碼轉換形式：

    (...)? (x / d + 0.5) : (x / d - 0.5);

數學上四捨五入的關係：[x-0.5, x+0.5) => x，而根據 C99 6.5.5 的敘述：

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

C 語言上的整數除法是將小數尾數去掉，所以正號除法約同於無條件捨去，於是如果我們對這個範圍增值位移 0.5：[x, x+1) => x 這樣的除法結果便會對應到四捨五入的結果。然而在計算機的將小數除法尾數去掉的結果，在負號除法上卻反而變成無條件進位的結果，所以負號運算我們改成減值位移：(x-1, x] => x 才會符合預期。

再來我們來看條件式：

        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \

前兩個條件式是為了檢查 x, divisor 的型態是否為無號整數：如果 x, divisor 的型態為有號整數，那結果為否；但是如果把 -1 轉型為無號整數，則會變成正數，並會使條件式為真。

第三個條件式判斷 x 和 divisor 正負是否同號。

2022q1 Homework3 (quiz3)

測驗 1 ：GENMASK

測驗 2 ：align down

測驗 3 ：Reverse Bits

測驗 4 ：foreach macro

測驗 5 ：29. Divide Two Integers

測驗 8 ：Binary search tree

測驗 9 ：ROUND_UP_TO_ALIGNMENT_SIZE

linux 中的 ALIGN

測驗 10 ：DIVIDE_ROUND_CLOSEST

Read more

Linux Kernel Power Management

vcam

2022q1 Homework3 (fibdrv)

kecho