---
tags: linux2022
---

# 2022q1 Homework (quiz4)
contributed by < `hankluo6` >
> [第 4 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz4)

## 測驗 `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 (EXP1) + 1;       
}

要得到 $\lceil \log_2{x} \rceil$ 相當於取得最高位元 0 的位置與 LSB 間的數字數量，所以可以用 binary search 的方法從 16, 8, 4, 2 位元間隔尋找。

15 行後 `x` 只剩兩個位元，所以需要 `(x >> 1)` 進行最後一次搜尋，並加上缺少的一次 `r |= shift`，可得出 `EXP1 = r | shift | (x >> 1)`

---

## 測驗 `2`

### 運作原理

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

#include <stddef.h>

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 ((EXP2) == 0) {
            x >>= shift;
            EXP3;
        }

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

    return o;
}

與前一題一樣，從 32, 16, 8, 4, 2 位元去尋找，所以當在搜尋範圍內有位元為 1 時，需要右移 `x` 並將結果加到回傳值 `o` 上。所以 `EXP2 = s & t`；而回傳值 `o` 則需加上對應的位元數，故 `EXP3 = o += shift`。

---

## 測驗 `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 sfccessfully
 * or return false.
 */
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

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

    return ret;
}

從結構可以看出 `foo_consumer` 透過 `next` 相連，所以 `for` 迴圈應該為遍歷所有的 `foo_consumer`，而這邊使用 pointer to pointer 當作 iterator，所以 `EXP4 = con = &(*con)->next`。`EXP5` 需要將刪除的 `foo_consumer` 後方的 element 接上，可得出 `EXP5 = fc->next`。

---