# 2019q1W7上：林聖堯
contributed by `Shengyuu`
###### tags: `Linux 核心設計 2019`

## 測驗 1
### 函式解析：
`find_next_bit` 這個函式是從給定的資料 `bitmap` 的起始點 `start` 開始找，找到第一個 `set bit` 及回傳該位址，反之，則回傳 `bitmap` 的最大邊界 `bits` 的位址

在 C 語言中想要一個 bit 一個 bit 逐一檢查事件非常沒有效率的事情，因為每次從記憶體取值的單位可能為 32 bits 或 64 bits 等等，但不會是 1 bit。因此在 `bits.c` 中是作這些 find bit 的函式都是透過 unsigned long 為單位，一次檢查 64 bits ，若 `find_next_bit` 發現要找的結果在某個 `set` 裡面，在從這個 `set` 裡找出第一個 1 的位址。

觀察 `bits.c` 會發現函式 `find_next_zero_bit`

static inline size_t find_next_zero_bit(const unsigned long *bitmap,
                                        size_t bits,
                                        size_t start)
{
    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);

    if (start >= bits)
        return bits;

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

    for (size_t i = first_long + 1; !t && i < l; i++) {
        /* search until valid t is found */
        long_lower += BITS_PER_LONG;
        t = bitmap[i];
        t ^= ~0UL;
    }

    if (!t)
        return bits;

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

    return pos;
}

此函式為求出字串中第一個為 0 的位址，和題目要求的 `find_next_bit` 相反。觀察此段程式碼會發現只要把判斷是否找到 `0` 的程式碼

t ^= ~0UL;

更改為是否找到 `1` 的程式碼

t ^= 0UL;

即可移植到 `find_next_bit` 函式中

### find_next_bit

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);
    t ^= 0UL;
    for (size_t i = first_long + 1; !t && i < l; i++) {
//        ...待補...
        long_lower += BITS_PER_LONG;
        t = bitmap[i];
        t ^= 0UL;
    }
    
    if (!t)
        return bits;

    size_t pos;
  //  ...待補...
    pos = long_lower + bitops_ffs(t) - 1;
    if (pos >= bits)
        return bits;
    return pos;
}

## 測驗 2
觀察程式碼會發現 `check_bits` 函式，`check_bits` 用另一個函式 `find_next` 來驗證我們實作的 `find_next_bit` 的結果是否正確。因此我們只要想辦法產生隨機的 `bitmap` 丟到 `check_bits` 函式即可驗證

想到隨機驗證，就會想用 `rand()` 函式來試驗，翻閱規格書後確定在 `gnu C libary` 內定義的 `rand()` 最大值為 32 bits singed int 的最大值，而 `test` 的型態是 `unsigned long` ，有 64 個位元，因此用 4 個 rand() * rand() 相加來產生一個 test 的 element

test[j] = rand() * rand() + rand() * rand()
+ rand() * rand() + rand() * rand();

### main 程式碼

int main(void) {
    srand(time(0));
    for(int i = 0; i < 1000; i++)
    {   
        for(int j = 0; j < BITS_TO_LONGS( MAX_TEST_BITS ); j++)
        {                                                                    
            test[j] = rand() * rand() + rand() * rand() 
                + rand() * rand() + rand() * rand(); 

        }
        check_bits(test, MAX_TEST_BITS);

    }
}

## 測驗 3
函式 `bitops_ffs` 呼叫巨集 `__builtin_ffsl(x)` ，上網查了一下得知此巨集的作用為 `Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.` ，

### `bitops_ffs`

static inline size_t bitops_ffs(unsigned long x) {
    for(int i = 0; i< 64; i++)
        if(x & (1UL << i)) return i + 1;
}

### `main`

int main()
{
    for(int i = 0; i < 64; i++)
        assert(bitops_ffs((1UL << i))-1 == i); 
    return 0;
}

## 測驗 4
### `bitops_ffz`

static inline size_t bitops_ffs(unsigned long x) {
    for(int i = 0; i< 64; i++)
        if(~x & (1UL << i)) return i + 1;
}

### `main`

int main()
{
    for(int i = 0; i < 64; i++)
        assert(bitops_ffs(~(1UL << i))-1 == i); 
    return 0;
}