# 2019q1W7上: 陳奕熹

## 測驗 `1`
請研讀原始程式碼和對應註解，補完 `find_next_bit` 函式的程式碼，確保符合 Linux 核心的 `find_next_bit` 語意並可通過 main 函式給定的測試。應用到 `bitops_ffs` 和確保新增的程式碼行數儘可能少。

static inline size_t find_next_bit(const unsigned long *bitmap,
                                   size_t bits,
                                   size_t start)
{
    unsigned long t;
    size_t l = BITS_TO_LONGS(bits);
    size_t first_long = start / BITS_PER_LONG;
    size_t long_lower = start - (start % BITS_PER_LONG);

    if (start >= bits)
        return bits;

    t = bitmap[first_long] & BITMAP_FIRST_WORD_MASK(start);
    for (size_t i = first_long + 1; !t && i < l; i++) {
        long_lower += BITS_PER_LONG;
        t = bitmap[i];
    }
    
    if (!t)
        return bits;

    size_t pos;
    pos = long_lower + bitops_ffs(t) - 1;
    if (pos >= bits)
        return bits;

    return pos;
}

解題方向：
1. 第一個參考資料有一點點幫助，但更多的是我看不懂他中文在寫啥
最後還是看 source code 比較快
2. 其實參考 `find_next_zero_bit()` 實做可以大概知道整體思路

    size_t pos;
    unsigned long t;
    size_t l = BITS_TO_LONGS(bits);
    size_t first_long = start / BITS_PER_LONG;
    size_t long_lower = start - (start % BITS_PER_LONG);

一開始的這部份把 bit-oriented 轉換成 long 表示（因為後面遞迴加的單位是 long），另外需要注意的是 `long_lower` 如同字面上意義，需要考慮到 start 並沒有與 long 做對齊的情況

    t = bitmap[first_long] | ~BITMAP_FIRST_WORD_MASK(start);
    t ^= ~0UL;

這邊則是因為考慮到開頭可能不對齊的現象，特別弄了一個 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 之位元內容)

int main(void) {
    srand(time(NULL));
    for (int i = 1; i < MAX_TEST_BITS; i++) {
        bitmap_fill(test, i);
         
        for (int j = 0; j < 7; j++) {
            size_t rand_factor = (rand() % 0xff) + 1;
            test[j] ^= rand_factor;
        }
        
        assert(find_next_bit(test, i, 0) == 0);

        bitmap_zero(test, i);
        assert(find_next_bit(test, i, 0) == i);
    }
    return 0;
}

目前這個版本會卡在 assert ，因為隨機亂數還不能確定答案
當然也是可以假設只有固定一個 1 下排列組合，但是這樣測試的數值覆蓋率實在不好
同時如果可以的話修改 `bitmap_fill` 本身應該可以減少程式指令的運用

#### 2019/04/16 更新
根據之前看開源專案的經驗，像這類驗證 function correctess (包含函示庫間獨立正確的 reliance) 都會額外寫 test function 引用這些函示庫做測試
因此比較理想的測試方式，應該是寫一個 tester function 拿到 `find_next_bit` 的回傳與已知正確的實作方法比較輸出

## 測驗 `3`
承測驗 `1`，用 C99 語法改寫 `bitops_ffs` 函式，使其不依賴 GNU extension，需要附上對應的測試程式碼。

int my_ffsl(unsigned long x) {
  int n = 1;
  if ((x & 0x00000000FFFFFFFF) == 0) {n = n + 32; x >>= 32;}
  if ((x & 0x000000000000FFFF) == 0) {n = n + 16; x >>= 16;}
  if ((x & 0x00000000000000FF) == 0) {n = n + 8; x >>= 8;}
  if ((x & 0x000000000000000F) == 0) {n = n + 4; x >>= 4;}
  if ((x & 0x0000000000000003) == 0) {n = n + 2; x >>= 2;}
  return n - (int)(x & 1) + 1;
}

其實 ffsl 計算「從右數過來第一個 1 的位置」這個問題等價於
「計算 tailing zero 的數目（再加一）」
以上程式碼主要是根據 [Implementing GCC's Builtin Functions](https://blog.stephencleary.com/2010/10/implementing-gccs-builtin-functions.html) 改成 long 版本的