---
tags: linux2022
---

# 2022q1 Homework4 (quiz4)
contributed by < `StevenChou499` >
* [作業需求](https://hackmd.io/@sysprog/BJJMuNRlq)
* [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz4)

---

## 測驗 `1`
> 延伸[第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)的測驗 `7` ，已知輸入必為大於 `0` 的數值 (即 `x > 0` )，以下程式碼可計算$[\log _{2} (x)]$，，也就是 [ceil](https://man7.org/linux/man-pages/man3/ceil.3.html) 和 [log2](https://man7.org/linux/man-pages/man3/log2.3.html) 的組合並轉型為整數:
> ```c
> 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;
> }
> ```
> 請補完，使其行為符合預期。作答規範:
> * `EXP1` 應以最簡潔的形式撰寫，且符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範 (近似 Linux 核心程式碼排版風格)
> * `EXP1` 為表示式，限制使用 `^` , `&` , `|` , `<<` , `>>` 這幾個運算子，可能會出現常數
> * `EXP1` 不該包含小括號 (即 `(` 和 `)` )
> * 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 `r` , `shift` , `x`
> * `EXP1` 不可包含 `,` 和 `;` 這樣的分隔符號 (separator)

### 思考與想法
本題與[測驗3](https://hackmd.io/@sysprog/linux2022-quiz3)的第 `7` 題其實非常相似，前面之時做方法其實都是相同的，只是因為這次需要搭配計算的是 [ceil](https://man7.org/linux/man-pages/man3/ceil.3.html) 的方式， 因此一開始需要先將數字 `x` 減 `1` ，最後在計算完之後再加上 `1` ，以避免在計算以 `2` 為底的對數時少算。而因為 `EXP1` 只需要計算最後一位，不需要經過計算相加並儲存，其值為 `r | shift | x >> 1` 。

:::success
EXP1 : r | shift | x >> 1
:::

---

## 測驗 `2`
> 複習〈[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)〉，改寫[第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)的測驗 `11` 裡頭的 fls 函式 (fls 意謂 "find last set")，使其得以計算 [Find first set](https://en.wikipedia.org/wiki/Find_first_set):
> ```c
> #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;
> }
> ```
> 請補完，使其行為符合預期。作答規範:
> `EXP2` 和 `EXP3` 應以最簡潔的形式撰寫，且符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範 (近似 Linux 核心程式碼排版風格)
> `EXP2` 和 `EXP3` 限制使用 ^, &, |, <<=, >>=, +=, -= 這幾個運算子，可能會出現常數
> `EXP2` 和 `EXP3` 不該包含小括號 (即 `(` 和 `)` )
> 為了自動批改的便利，變數出現的順序 (可從缺) 從左到右為 `x` , `o` , `t` , `shift` ，也就是說，你應該寫 `x ^ t` 而非 `t ^ x`
> `EXP2` 和 `EXP3` 不可包含 `,` 和 `;` 這樣的分隔符號 (separator)

### 思考與想法

---

## 測驗 `3`
> 考慮以下改寫自 Linux 核心的程式碼:
> ```c
> 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;
> }
> ```
> 請補完，使 `consumer_del` 行為符合註解規範。作答規範:
> 1. `EXP4` 和 `EXP5` 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
> 2.`EXP4` 和 `EXP5` 都包含指標操作 (如 `->`)

### 思考與想法
題目使用了 `pointer to a pointer` 的方式循序訪問各個 `foo_consumer` ，並比較之後若相同則刪除該 `foo_consumer` ，回傳 `true` 。因此 `EXP4` 之值應該為讓 `for` 迴圈跳往下個 `foo_consumer` 的 `con = &(*con)->next` ，而 `EXP5` 之值應該為 `con = &(*con)->next` ，才可以跳過想要刪除的點而直接連接至下一個 `foo_consumer` 。

:::success
EXP4 : con = &(*con)->next
EXP5 : con = &(*con)->next
:::

## 測驗 `4`