# 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負數。
## 測驗 `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的方法，每次都找**一半**。
## 測驗 `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。
>上述方法可以應用在各種 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));
```
先撇開三元條件式，上述程式碼是要去計算除法且**四捨五入後**的結果。
:::danger
改用 Graphviz 或 HackMD 支援的標記語法來製圖
:notes: jserv
:::
根據上述的範例得知，可以先讓被**除數(x)先加除數(divisor)的一半**，再去做C的整數除法，就能做到四捨五入了。但是上述想法只用於正數除法，**負數除法則是要先減再除**，答案才會對。
Sign in with Wallet
Connect another wallet