Try   HackMD

2022q1 Homework4 (quiz4)

contributed by < jim12312321 >

測驗題目

測驗 1 ： ceil
log2


















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;       
}

解析：
這題跟 第三周測驗題第 7 題想法上大致一致，一樣是用 binary search，每次對半檢查，檢查當前 bits 中的上半部分是否有值，之後再位移 x 並將結果相加得到答案。

不要加上「的概念」，本質上就是 binary search!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

本題在第 14 行時檢查到 0x3 ，也就是剩最後兩個 bits ，經過位移後就回傳答案了，因此我們可知題目將以下步驟濃縮在 (EXP1)+1 中。




r |= shift;
shift = (x > 0x1) << 0; //為了寫法一致，所以加上 `<< 0`
r |= shift;

其中第三行中的 shift 可以直接用 (x > 1) 取代，因此目前可以簡化成

↓

r |= (shift | (x > 1));

而又因為現在的 x 只剩 2 個 bits ，因此判斷是否大於 1 等價於右移 1 ，程式碼可以進一步簡化

↓

r |= (shift | (x >> 1));

EXP1

→ r | shift | x >> 1

延伸問題 2

改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless






































int ceil_log2(u_int32_t x)
{
    u_int32_t r, shift;
    /*if input 0,than x will be 0xFFFFFFFF*/
    x--;
    r = (x > 0xFFFF) << 4;
    x >>= r;
    /* let x still be 0xFFFFFFFF if input 0*/
    x <<= (x == 0xFFFF) << 4;
    x += (0xFFFF & -(x == 0xFFFF0000));
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    /* let x still be 0xFFFFFFFF if input 0*/
    x <<= (x == 0xFFFFFF) << 3;
    x += (0xFF & -(x == 0xFFFFFF00));
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    /* let x still be 0xFFFFFFFF if input 0*/
    x <<= (x == 0xFFFFFFF) << 2;
    x += (0xF & -(x == 0xFFFFFFF0));
    shift = (x > 0x3) << 1;
    x >>= shift;
    r |= shift;
    /* let x still be 0xFFFFFFFF if input 0*/
    x <<= (x == 0x3FFFFFFF) << 1;
    x += (0x3 & -(x == 0xFFFFFFFC));
    r |= shift;
    shift = (x > 0x1) << 0; 
    x >>= 1;
    r |= shift;
    /* let x still be 0xFFFFFFFF if input 0*/
    x <<= (x == 0x7FFFFFFF) << 1;
    x += (0x1 & -(x == 0xFFFFFFFE));
    return (r | x )+1;
}

主要想法就是針對輸入 0 這個特例進行處理。
一開始的 x--會使值從 0 變為 0xFFFFFFFF ，之後每次位移後都將值補回去讓其隨時都為 0xFFFFFFFF ，最後 0xFFFFFFFF +1 就會等於 0。

思考如何藉由巨集來簡化程式碼，注意 bitmask/generator 的設計

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

測驗 2 ： find first set






























#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;
}

解析：
這題一樣是利用 binary search ，每次對半檢查 x 中的下半部 (e.g. 假設現在 x 為 16 bits ，那下半部就是第 0 到 7 個 bits) 是否有值，若有值則表示應該繼續找下去，若沒有值則表示 first set bit 在目前的上半部，因此要將當前字串右移並累加結果。
EXP2

→ x & t
EXP3
→ o += shift

延伸問題 1

迴避 while, for, goto 等關鍵字以改寫出功能等價的實作

naïve 版本：
因為本質上是 binary search ，而對於 unsigned long (64 bits in LP64) 中最多就是重複 6 次，直接展開即可。






















































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;
    if ((x & t) == 0) {
        x >>= shift;
        o += shift;
    }

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

    return o;
}

遞迴版本：
除了比較簡短之外，對應不同型態的數值也不用重新思考要對切幾次，可以直接修改 BITS_PER_LONG, t, x 的資料型態即可，另外要特別注意，因為希望在遞迴執行時 shift, t, o 不用特別傳入且始終為同一個，因此變數宣告時要加上 static 修飾詞。























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

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

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

    if(shift){
        ffs(x);
    }else{
        return o;
    }
}

暫時想不到更精簡的寫法了。

延伸問題 2

在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例

在 include/asm-generic/bitops 中可以看到許多相關實現方法，如： __ffs, __fls, ffs, fls 等方法。

我們來追蹤 __ffs 的應用情境，可以在 drivers/clk/ti/clkt_dpll.c 中的 _omap2_dpll_is_in_bypass 找到他。




























/**
 * _omap2_dpll_is_in_bypass - check if DPLL is in bypass mode or not
 * @v: bitfield value of the DPLL enable
 *
 * Checks given DPLL enable bitfield to see whether the DPLL is in bypass
 * mode or not. Returns 1 if the DPLL is in bypass, 0 otherwise.
 */
static int _omap2_dpll_is_in_bypass(u32 v)
{
	u8 mask, val;

	mask = ti_clk_get_features()->dpll_bypass_vals;

	/*
	 * Each set bit in the mask corresponds to a bypass value equal
	 * to the bitshift. Go through each set-bit in the mask and
	 * compare against the given register value.
	 */
	while (mask) {
		val = __ffs(mask);
		mask ^= (1 << val);
		if (v == val)
			return 1;
	}

	return 0;
}

就像註解所說的，在這裡 __ffs 的目的就是為了從 mask 的高位 set bit 逐步走訪所有 set bit (而 mask ^= (1 << val); 就是為了消除找到的 first set bit) 並且判斷是否為 bypass mode 。

測驗 3 ︰ a pointer of a pointer

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;
}

解析︰
這題只是單純考驗指標的指標運用技巧，在 comsumer_del 中需要走訪 foo->comsumers 找到指定移除的結點 fc 。
所以我們知道在 EXP4 中需要讓 con 繼續走訪 linked list 並在 EXP5 時移除找到的結點。

EXP4

→ con = &(*con)->next
EXP5
→ fc->next

另外在延伸問題 1 中也要求以下問題

↓

區分 foo 和 foo_consumer 的好處

我認為這樣的用意主要是為了封裝，模組化比起大雜燴來得好維護，另一個好處則是增加程式易讀性，方便理解和維護。

測驗 4 ︰ coroutine













static void task_switch(struct list_head *tasklist)
{
    jmp_buf env;

    if (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP6;
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}













static void task_join(struct list_head *tasklist)
{
    jmp_buf env;

    while (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP7;
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

在 task_switch 和 task_join 中都需要將當前的 task 從 task list 中移除。

EXP6

→ list_del(&t->list)
EXP7
→ list_del(&t->list)

























void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        EXP8;
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

























void task1(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 1: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        EXP9;
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 1: resume\n");
    }

    printf("Task 1: complete\n");
    longjmp(sched, 1);
}

在 task0 或 task1 中執行完 task_add 後需要返回到 schedule 中。

EXP8

→ longjmp(sched, 1)
EXP9
→ longjmp(sched, 1)

測驗 5 ： READ_ONCE










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

union 有別於 struct 的特點在於 union 所佔的記憶體空間大小以 union 中占最大空間的成員，因此 DECL0 需要選擇所占空間最小的型態。
DECL0

→ char __c[1]

Last changed by 
 
白耀升
0
280
Published on HackMD