owned this note
owned this note
Published
Linked with GitHub
---
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`