---
tags: linux kernel
---
# 2022q1 Homework3 (quiz3)
contributed by <`zoanana990`>
## 測驗 `1`
## 測驗 `3`
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```c
#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;
}
```
這題為[你所不知道的C語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)的簡化版，原版為
```
new = num;
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);
```
上面過程如下所示，以 `0x12345678` 為例：
```text
bit 3 2 1 0
original number 1 2 3 4 5 6 7 8
0001 0010 0011 0100 0101 0110 0111 1000
1st switch (16 bits) 0101 0110 0111 1000_0001 0010 0011 0100
2nd switch (8 bits) 0111 1000_0101 0110 0011 0100_0001 0010
3rd switch (4 bits) 1000_0111 0110_0101 0100_0011 0010_0001
4th switch (2 bits) 0010 1101 1001 0101 0001 1100 1000 0100
5th switch (1 bit) 0001 1110 0110 1010 0010 1100 0100 1000
result 1 e 6 a 2 c 4 8
```
由上可知，程式碼會是對半調換，將程式碼簡化為 `uint8_t` ， 原理相同
::: info
問題:
- [x] 補完程式碼
- [x] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
---
## 測驗 `5`
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```c
#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;
}
```
這題為[你所不知道的C語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)的簡化版，原版為
```
new = num;
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);
```
上面過程如下所示，以 `0x12345678` 為例：
```text
bit 3 2 1 0
original number 1 2 3 4 5 6 7 8
0001 0010 0011 0100 0101 0110 0111 1000
1st switch (16 bits) 0101 0110 0111 1000_0001 0010 0011 0100
2nd switch (8 bits) 0111 1000_0101 0110 0011 0100_0001 0010
3rd switch (4 bits) 1000_0111 0110_0101 0100_0011 0010_0001
4th switch (2 bits) 0010 1101 1001 0101 0001 1100 1000 0100
5th switch (1 bit) 0001 1110 0110 1010 0010 1100 0100 1000
result 1 e 6 a 2 c 4 8
```
由上可知，程式碼會是對半調換，將程式碼簡化為 `uint8_t`
::: info
問題:
- [x] 補完程式碼
- [x] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
---
## 測驗 `9`
```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))
```
:::info
- [x] 補完程式碼
- [x] 解釋上述程式碼運作原理，並撰寫出對應 ROUND_DOWN 巨集
- [x] 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合
:::
- 解釋這個程式碼的原理
- 首先以本程式為例，先羅列出我們想要什麼
- `16` 是我們想要統一的尺寸，也就是不管我們輸入什麼我們都必須回傳16，因此最好的方法是將 `16` 的那個位元組保留下來，其他歸零
```
16: 1 0 0 0 0
int: 0 0 1 0 0
char: 0 0 0 0 1
15: 0 1 1 1 1
--------------------------------
int+15: 1 0 0 1 1
char+15: 1 0 0 0 0
&(~15): 1 0 0 0 0
--------------------------------
Output: 1 0 0 0 0
```
- `ROUND_UP` 程式碼
```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 - 1) & (~(MAX_ALIGNMENT - 1)))
```
- `ROUND_DOWN` 實作
```c
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \
(((x) ) & (~(MAX_ALIGNMENT - 1)))
```
- 這裡程式碼不需要先把原本的 `type` 相加，直接消除即可
- `linux` 中的 `round_up/down` 函式，位於 `linux/include/linux/math.h`
```c
#define __round_mask(x, y) ((__typeof__(x))((y)-1))
#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
#define round_down(x, y) ((x) & ~__round_mask(x, y))
```
- 測試程式碼
```c
int main(){
int x = 20;
int y = MAX_ALIGNMENT;
printf("x = %d, y = %d, round_up = %d, round_down = %d, \
ROUND_UP_TO_ALIGNMENT_SIZE = %d, \
ROUND_DOWN_TO_ALIGNMENT_SIZE = %d\n", \
x, y, round_up(x, y), round_down(x, y), \
ROUND_UP_TO_ALIGNMENT_SIZE(x), \
ROUND_DOWN_TO_ALIGNMENT_SIZE(x));
return 0;
}
```
- 結果
```c
x = 20, y = 16,
round_up = 32, round_down = 16,
ROUND_UP_TO_ALIGNMENT_SIZE = 32,
ROUND_DOWN_TO_ALIGNMENT_SIZE = 16
```
- 這個函式的應用在 `stack` 存放訊號時，如以下程式碼
```c
static unsigned long align_sigframe(unsigned long sp)
{
#ifdef CONFIG_X86_32
/*
* Align the stack pointer according to the i386 ABI,
* i.e. so that on function entry ((sp + 4) & 15) == 0.
*/
sp = ((sp + 4) & -FRAME_ALIGNMENT) - 4;
#else /* !CONFIG_X86_32 */
sp = round_down(sp, FRAME_ALIGNMENT) - 8;
#endif
}
```
---
## 測驗 `10`
```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)); \
})
```
:::info
- [ ] 補完程式碼
- [ ] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心找出類似的巨集和程式碼，說明 `div round-up/closest` 的應用場合
:::
---
## 測驗 `11`
Sign in with Wallet
Connect another wallet