2024q1 第 18 週測驗題

目的: 檢驗學員對 bitwise operation 的認知

作答表單 (針對 Linux 核心「實作」課程)

測驗 1

延伸〈Linux 核心原始程式碼的整數除法〉和第 7 週測驗 2，fastdiv (部分程式碼遮蔽) 提出快速除法實作。以下是測試程式碼:

#include <assert.h>
#include <stdio.h>

#include "fastdiv.h"

int main(int argc, char **argv)
{
    const uint64_t MAX_NUM = 1 << 16;
    const uint64_t MAX_DIV = 1 << 14;

    for (uint64_t d = 1U; d < MAX_DIV; ++d) {
        div_t fd;        /* general method */
        fastdiv(&fd, d); /* divide-by-d */
        const uint64_t mul = fd.mul, add = fd.add, shift = fd.shift;

        div_t fd2;                         /* bounded method optimization */
        fastdiv_bounded(&fd2, d, MAX_DIV); /* divide-by-d */
        const uint64_t mul2 = fd2.mul, add2 = fd2.add, shift2 = fd2.shift;
        assert(mul2 == 1U || add2 == 0U || shift2 == 0U);
        assert(add2 == 0U);
        for (uint64_t num = 0; num < MAX_NUM; ++num) {
            const uint64_t normal = num / d;
            const uint64_t general = (num * mul + add) >> shift;
            const uint64_t bounded = (num * mul2) >> shift2;
            assert(general == normal);
            assert(bounded == normal);
        }
    }
}

請補完程式碼，使 assert 巨集不會在執行時期觸發錯誤並運作符合預期。作答規範:

• AAAA, BBBB, CCCC, DDDD 皆為整數
• 不該存在小括號 (即 ( 和 ))，以最精簡的形式書寫

延伸問題:

1. 解釋上述程式碼運作原理，設計實驗來比較除法和 fastdiv 的效率，並試圖解釋其行為
2. 以 jemalloc 為例，解說快速除法運算的應用場景。嘗試在 Linux 核心原始程式碼找出類似的技巧
3. GCC Bug #89845 提及針對整數除法的加速機制，參照到 Faster Remainder by Direct Computation Applications to Compilers and Software Libraries，嘗試解讀其手段並舉例說明
4. libdivine 提供更進階的除法加速機制，嘗試解釋其原理