---
# System prepended metadata

title: 2022q1 Homework3 (quiz3)

---

# 2022q1 Homework3 (quiz3)
contributed by < `happyjack91630` >
> [作業需求](https://hackmd.io/@sysprog/BJJMuNRlq)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
## 測驗 `1` ：GENMASK
:::success
EXP1 = 63 - h
EXP2 = l
:::
產生連續的 bitmask。
```c
#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
    //(~0UL = 1111...111)
```
例如:
* `GENMASK(6, 4)` 產生 01110000 
* `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)

`GENMASK(h, l)` 可以看出就是在h ~ l + 1 位元以外的地方都是0。

`((~0UL) >> (LEFT)`的作用是將63 ~ h位元設成0，所以`LEFT = 63 - h`。
`(~0UL) >> (l) << (RIGHT))`的作用是將 l - 1 ~ 0位元設成0，所以`RIGHT = l`。
`((~0UL) >> (63 - h)` 跟 `(~0UL) >> (l) << (l))`做 and 運算，就能將h ~ l + 1，l - 1 ~ 0 位元清除成0，保留其他位元為1。

## 測驗 `2` ：align down
>參考 `kevinshieh0225`
:::success
EXP1 = (struct foo *)(v & -3)
:::
```c=
struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

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

我們希望將`to_fd`指派在地址`v`且向下對齊的位置上。舉例來說，v = 7，向下對齊要變成4，v = 15，向下對齊要變成12，所以比v小的最大4的倍數。(v & ~3)就能取到比v小且為4的倍數。但是`struct fd`裡第一個存的是`struct foo *foo`，所以要將`v`轉型成`struct foo`的型態。


## 測驗 `3` ：Reverse Bits
:::success
EXP2 = (x & 0x33) << 2
EXP3 = (x & 0x55) << 1
:::
```c
#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;
}
```

這裡我用 `x = 12345678`當作以下解釋程式碼的範例。
```c
#include <stdint.h>
//每次都取一半來做反轉
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);
    // (12345678 >> 4) | (12345678 << 4) = 56781234 
    x = ((x & 0xCC) >> 2) | (EXP2);
    // ((56781234) & 11001100) >> 2) | ((56781234) & 00110011)) << 2  = 78563412
    x = ((x & 0xAA) >> 1) | (EXP3);
    // ((78563412) & 10101010) >> 1  | ((78563412) & 01010101)  << 1  = 87564321
    return x;
}
```

:::warning
避免說「一半」這種詞彙，請將自己設想在「科技公司面試場合」，用字要精準，無論你如何位移，資料寬度仍是一致，因此跟「一半」的概念不同。
:notes: jserv
:::

## 測驗 `4` ： foreach 巨集
>參考`hsuedw`
:::success
EXP4 = ++_foreach_i
EXP5 = ++_foreach_i
:::
>
延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:
```c=
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);
}
```
對應的巨集定義:
```c=
#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__})))
```
```c=
int i;
foreach_int(i, 0, -1, 100, 0, -99) {
    printf("i is %i\n", i);
}
```
先針對上述的`foreach_int(i, 0, -1, 100, 0, -99)`做解析，利用相關巨集定義做展開，對展開一項一項做解析。
```c=
int i;
for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); (i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]) {
    printf("i is %i\n", i);
}
```
* `(int[]){0, -1, 100, 0, -99})` 表示宣告一個int array，裡面包了這5個元素。
* `((int[]){0, -1, 100, 0, -99})[0]` 表示取這個array的第0個index的值，也就是0。
* `((i) = ((int[]){0, -1, 100, 0, -99})[0])` 表示將這個array的第0個index的值，assign給i。
* `unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0)` ，這段程式碼可以看做成`unsigned _foreach_i = (0, 0)`，第一個0的由來是取第0個index的值，第二個0可以看成是將`_foreach_i`的初始值設為0。
* `_foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int);` 這個為for loop的中止條件，_foreach_i(index)要小於array的長度。
* `(i) = ((int[]){0, -1, 100, 0, -99,0})[EXP4]` for迴圈有了初始條件，有了終止條件，剩下的就是要做`_foreach_i(index)`的狀態變化。那這題是要將`_foreach_i`做遞增，讓array跑完。`EXP4 = ++_foreach_i`。

那第二個巨集`foreach_ptr`就跟上述想法一致，所以`EXP5 = ++_foreach_i`



## 測驗 `5` ：LeetCode 29. Divide Two Integers
:::success
EXP6 = dvs << shift
EXP7 = dvd -= dvs << shift
:::
針對 LeetCode 29. Divide Two Integers，以下是可能的實作:
```c=
#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;
}
```
* 第4行到第15行的程式碼要先辨識出最後的答案是正數還是負數。
* 第17行到第27行的程式碼就是在做除法運算，res會是商，那EXP7則是算餘數是多少。
* 第29行到第32行則是再把結果，變成正數or負數。
![](https://i.imgur.com/pQ3RLvd.png)

## 測驗 `7` ：ilog32
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```c=
int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4; //0xFFFFU = 0x0000FFFF
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}
```
這題換句話說，就是要取2進位，最高位元的1在甚麼地方?這邊用的方法，類似於binary search的方法，每次都找**一半**。 
![](https://i.imgur.com/4JydSZr.png)



## 測驗 `9` ：ROUND_UP_TO_ALIGNMENT_SIZE
:::success
MMM = 1
NNN = MAX_ALIGNMENT - 1
:::
考慮以下進行記憶體地址對齊 (alignment) 的巨集:
```c=
/* 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))
```
這題是要考記憶體對齊，對齊的單位為16，也就是要補滿到最近的16倍數，例如 7 => 16，15 => 16，29 => 32，換句話說，就是要無條件進位到16的倍數。要將 x 進位到 16 倍數的想法就是，先 x + 15 再將後面3個bit(bit 0 ~ 3)清成0。
![](https://i.imgur.com/JsIAep7.png)
>上述方法可以應用在各種 2 的冪進位系統上。

## 測驗 `10` ：DIVIDE_ROUND_CLOSEST
:::success
RRR = __x + (__d >> 1)
SSS = __x - (__d >> 1)
:::
此題實作整數除法取近似整數。
```c
#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));                 \
    })
```
原本C的整數除法是**無條件捨去法**，這題的函示要做的除法是**四捨五入**。
```c=
typeof(x) __x = x   
typeof(divisor) __d = divisor; 
```
上述宣告方式是要避免巨集展開時，導致多次的evalution，所以才先將x跟divisor的值放入另一個參數中，防止變數被更改到(之所以要檢查是否為 unsigned ，是因為跟 unsigned 運算的 signed 數值也會變 unsigned ，因此恆大於等於 0)。

```c=
 (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         
```
>參考`jim12312321`
這條件式主要是先判斷結果有沒有可能是負數，是結果採用**正數除法**還是**負數除法**。x 如果為int，代表typeof((x) - 1 > 0)不成立，那如果 x 為unsigned int ，代表typeof((x) - 1 > 0)成立。
```c=
((RRR) / (__d)) 
((SSS) / (__d));  
```

先撇開三元條件式，上述程式碼是要去計算除法且**四捨五入後**的結果。

![](https://i.imgur.com/U181hTf.png)
:::danger
改用 Graphviz 或 HackMD 支援的標記語法來製圖
:notes: jserv
:::

根據上述的範例得知，可以先讓被**除數(x)先加除數(divisor)的一半**，再去做C的整數除法，就能做到四捨五入了。但是上述想法只用於正數除法，**負數除法則是要先減再除**，答案才會對。