# 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 的指數，也就是說取得的是 $\lfloor log_2(x) \rfloor$， 但為了避免 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;                                  \
    })