1
請研讀原始程式碼和對應註解,補完 find_next_bit
函式的程式碼,確保符合 Linux 核心的 find_next_bit
語意並可通過 main 函式給定的測試。應用到 bitops_ffs
和確保新增的程式碼行數儘可能少。
解題方向:
find_next_zero_bit()
實做可以大概知道整體思路一開始的這部份把 bit-oriented 轉換成 long 表示(因為後面遞迴加的單位是 long),另外需要注意的是 long_lower
如同字面上意義,需要考慮到 start 並沒有與 long 做對齊的情況
這邊則是因為考慮到開頭可能不對齊的現象,特別弄了一個 BITMAP_FIRST_WORD_MASK 以取得 start 對齊後的位元
這邊的 t 只要不為零(全部的 bit 都是零),就是為找到答案 (!t
只要為 1 就代表根本沒有 bit set)
t ^= ~0UL;
這一步是為了把 01 互換以取得 0 的位置 (跟 0xFFFFFFF 做「異或」其實就是求 1 補數)
但是在 find_next_bit()
因為已經是 1 就不需要額外做這個操作
其後只要注意到 t ^= ~0UL;
這步驟比較不同外,其他概念上是大致相同的
2
承測驗 1
,改寫 main
函式,強化測試的強度,允許檢驗隨機的 BITMAP test 組合 (也就是需要隨機變更 test 之位元內容)
目前這個版本會卡在 assert ,因為隨機亂數還不能確定答案
當然也是可以假設只有固定一個 1 下排列組合,但是這樣測試的數值覆蓋率實在不好
同時如果可以的話修改 bitmap_fill
本身應該可以減少程式指令的運用
根據之前看開源專案的經驗,像這類驗證 function correctess (包含函示庫間獨立正確的 reliance) 都會額外寫 test function 引用這些函示庫做測試
因此比較理想的測試方式,應該是寫一個 tester function 拿到 find_next_bit
的回傳與已知正確的實作方法比較輸出
3
承測驗 1
,用 C99 語法改寫 bitops_ffs
函式,使其不依賴 GNU extension,需要附上對應的測試程式碼。
其實 ffsl 計算「從右數過來第一個 1 的位置」這個問題等價於
「計算 tailing zero 的數目(再加一)」
以上程式碼主要是根據 Implementing GCC's Builtin Functions 改成 long 版本的