2022q1 Homework4 (quiz4)

contributed by < cyrong >

測驗`1`

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x >> 1) + 1;       
}

在此程式中使用了 4 個數字作為類似 bitmask 的作用
分別是 0xFFFF , 0xFF, 0xF, 0x3
將他們以 2 進位在 32 位元表示的話
0xFFFF : 0000 0000 0000 0000 1111 1111 1111 1111
0x00FF : 0000 0000 0000 0000 0000 0000 1111 1111
0x000F : 0000 0000 0000 0000 0000 0000 0000 1111
0x0003 : 0000 0000 0000 0000 0000 0000 0000 0011

以這些數字每次將位元數分成兩半，讓變數 r 紀錄 ceil_log2 值中 2 的冪的部份。

而 shift 最終會有兩種結果，分別是 0, 2，是在程式碼第 14 行處決定最後的值， shift 會從 0 開始分別在 x 的值在 2 的偶數次方之後交替，也就是

x = 2(

2^{0} + 1

) ~ 4(

2^{2}

), shift = 0
x = 5(

2^{2} + 1

) ~ 16(

2^{4}

), shift = 2
x = 17(

2^{4} + 1

) ~ 64(

2^{6}

), shift = 0
x = 65(

2^{6} + 1

) ~ 256(

2^{8}

), shift = 2

以此類推，shift 用意在於紀錄 r 所紀錄不到的 ceil_log2 中 2 的倍數的部份。

最後是 x ， x 最終會有三種結果，分別是 1, 2, 3，原因是經過程式碼中 7, 9, 12, 15行，若是符合條件 x 將分別被向右移 16, 8, 4, 2位元，因此最終只會存在 x 的前兩位元，又因為 x > 1，因此只會有 1, 2, 3 三種可能，觀察這三個值

1_{10}

01_{2}

2_{10}

10_{2}

3_{10}

11_{2}

當 x = 2, 3 時，代表 ceil_log2 的值會比 x = 1 時多 1 ，因此在回傳時將 x 向右位移以得知 x 是否為 2 或 3 。

而在 return 的最後的地方 +1 其用意在於取 ceiling 的部份，上述程式碼可以計算出的值為 x 中包含的 2 的指數，也就是說取得的是

⌊ l o g_{2} (x) ⌋

，但為了避免 2 的指數(

2^{n}

)被計算錯誤為 (

2^{n + 1}

)，因此在程式碼最開始有 x--

測驗 2






























#include <stddef.h>

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)


static inline size_t ffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t o = 1;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

    shift >>= 1;
    t >>= shift;

    while (shift) {
        if ((x & t) == 0) {
            x >>= shift;
            o += shift;
        }

        shift >>= 1;
        t >>= shift;
    }

    return o;
}

第 16 行先將 shift 往右位移 1 位，因此 shift 的值會是 BITS_PER_LONG >> 1 ，也就是 64 >> 1 = 32 ， t 中的值會是前 32 位元為 0 後 32 位元為 1 。

而在後面的 while 迴圈中，每次將 shift 向右位移 1 位、 t 向右位移 shift 位，這樣的操作下會把 t 的位元中 1 的個數每次減半

while 迴圈中對於 x, o 的操作則是用 t 判斷 x 中值為 1 最低位元位置，
若是 x & t == 0 代表 x 中值為 1 的最低位元在 t 的位元中的左半邊 0 的區域，這時就將 x 向右位移 shift 位並且將 o += shift ，也就是將 x 中在最低位元為 1 右側的 shift 個 0 給消除，並用 o 將消除掉的個數進行紀錄。

最終會紀錄下消除掉的 0 的個數，但因為 ffs 要尋找的是第一個 1 的位置，因此 o 的初始值為 1。

測驗 3

































struct foo_consumer {
    int (*handler)(struct foo_consumer *self, void *);
    struct foo_consumer *next;
};

struct foo {
    struct foo_consumer *consumers;
    unsigned long flags;
};

#include <stdbool.h>

/*
 * For foo @foo, delete the consumer @fc.
 * Return true if the @fc is deleted successfully
 * or retrun false.
 */

static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

    for (con = &foo->consumers; *con, con = &(*con)->next) {
        if (*con == fc) {
            *con = fc->next;
            ret = true;
            break;
        }
    }

    return ret;
}

測驗 5

#include <stdint.h>
#include <string.h>                       
#include <stdlib.h>

#define __READ_ONCE_SIZE                                  \
    ({                                                    \
        switch (size) {                                   \
        case 1:                                           \
            *(uint8_t *) res = *(volatile uint8_t *) p;   \
            break;                                        \
        case 2:                                           \
            *(uint16_t *) res = *(volatile uint16_t *) p; \
            break;                                        \
        case 4:                                           \
            *(uint32_t *) res = *(volatile uint32_t *) p; \
            break;                                        \
        case 8:                                           \
            *(uint64_t *) res = *(volatile uint64_t *) p; \
            break;                                        \
        default:                                          \
            memcpy((void *) res, (const void *) p, size); \
        }                                                 \
    })

static inline void __read_once_size(const volatile void *p, void *res, int size)
{
    __READ_ONCE_SIZE;
}

#define READ_ONCE(x)                                \
    ({                                              \
        union {                                     \
            typeof(x) __val;                        \
            char __c[1];                            \
        } __u;                                      \
        __read_once_size(&(x), __u.__c, sizeof(x)); \
        __u.__val;                                  \
    })

2022q1 Homework4 (quiz4)

測驗1

測驗 2

測驗 3

測驗 5

測驗`1`