2022q1 Homework3 (quiz3)

contributed by <zoanana990>

測驗 `1`

測驗 `3`

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. 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;
}

這題為你所不知道的C語言：數值系統篇的簡化版，原版為

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 為例：

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 ，原理相同

問題:

補完程式碼
解釋上述程式碼運作原理
在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 `5`

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. 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;
}

這題為你所不知道的C語言：數值系統篇的簡化版，原版為

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 為例：

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

問題:

補完程式碼
解釋上述程式碼運作原理
在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 `9`

/* 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))

補完程式碼
解釋上述程式碼運作原理，並撰寫出對應 ROUND_DOWN 巨集
在 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 程式碼

/* 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 實作

#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \
(((x) ) & (~(MAX_ALIGNMENT - 1)))

這裡程式碼不需要先把原本的 type 相加，直接消除即可

linux 中的 round_up/down 函式，位於 linux/include/linux/math.h

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

測試程式碼

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

結果

x = 20, y = 16, 
round_up = 32, round_down = 16, 
ROUND_UP_TO_ALIGNMENT_SIZE = 32, 
ROUND_DOWN_TO_ALIGNMENT_SIZE = 16

這個函式的應用在 stack 存放訊號時，如以下程式碼

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`

#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));                 \
    })

補完程式碼
解釋上述程式碼運作原理
在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合

2022q1 Homework3 (quiz3)

測驗 1

測驗 3

測驗 5

測驗 9

測驗 10

測驗 11

Read more

biRISC-V

Linux patch 心得

Linux 檔案系統

RISCV ISA

測驗 `1`

測驗 `3`

測驗 `5`

測驗 `9`

測驗 `10`

測驗 `11`