---
# System prepended metadata

title: 2022q1 Homework3 (quiz3)
tags: [linux kernel]

---

---
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`